Scaling models and data for solving large sparse
linear systems: a comparison of methods

Cedric Doucet
Cedrat SA 15, Chemin de Malacher 38240 Meylan
cedric.doucet@cedrat.com
I. Charpentier, J.-L. Coulomb, C. Guerin

As industrial problems may involve different kinds of physical parameters and different types of coupled equations, ill-conditioned sparse linear systems may arise from the discretization method. Let $ Au=f$ be a nonsingular sparse linear system where $ A\in \mathbb{C}^{n\times n}$, and $ u,f\in \mathbb{C}^n$. If the spectral condition number $ \kappa(A)$ is too far from one, direct solvers can lack of accuracy and iterative methods can fail to converge. An economical way of avoiding these difficulties is to find two diagonal matrices $ D_r$ and $ D_c$ such that $ \kappa(D_rAD_c) \approx \min_{D_1,D_2} \kappa(D_1A,D_2)$. Then, the solving process becomes

  1. compute $ \hat{u}$ such that $ \hat{A}\hat{u}=\hat{f}$
  2. compute $ u = D_c\hat{u}$
where $ \hat{A}= D_rAD_c$ and $ \hat{f}=D_rf$. Numerical properties of $ \hat{A}$ differ according to the scaling method; it can have normalized rows/columns [2] or it can be approximately doubly stochastic [3]. Other methods make the matrix have arbitrary row/column sums [1]. In this paper, we propose to make clear the interests of scaling corrections for supernodal and multifrontal direct solvers and for preconditioned iterative methods on industrial applications based on Maxwell equations (coupled problems, nonlinear materials, moving structures, transient problems) and discretized by means of nodal or edge finite elements.

[1] N. Linial, A. Samorodnitsky, A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Combinatorica 20 (200) 531-544.

[2] O. E. Livine, G. H. Golub, Scaling by Binormalization.

[3] D. Ruiz, A Scaling Algorithm to Equilibrate Both Rows and Columns Norms in Matrices, RAL-TR-2001-034.