OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

A Symmetry Preserving Algorithm for Matrix Scaling

Knight, Philip A. and Ruiz, Daniel and Uçar, Bora A Symmetry Preserving Algorithm for Matrix Scaling. (2014) SIAM Journal on Matrix Analysis and Applications, 35 (3). 931-955. ISSN 0895-4798

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://doi.org/10.1137/110825753


We present an iterative algorithm which asymptotically scales the∞-norm of eachrow and each column of a matrix to one. This scaling algorithm preserves symmetry of the originalmatrix and shows fast linear convergence with an asymptotic rate of 1/2. We discuss extensions of thealgorithm to the 1-norm, and by inference to other norms. For the 1-norm case, we show again thatconvergence is linear, with the rate dependent on the spectrum of the scaled matrix. We demonstrateexperimentally that the scaling algorithm improves the conditioning of the matrix and that it helpsdirect solvers by reducing the need for pivoting. In particular, for symmetric matrices the theoreticaland experimental results highlight the potential of the proposed algorithm over existing alternatives.

Item Type:Article
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > Ecole Normale Supérieure de Lyon - ENS de Lyon (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Institut National de la Recherche en Informatique et en Automatique - INRIA (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université Claude Bernard-Lyon I - UCBL (FRANCE)
Other partners > Université de Lyon - UDL (FRANCE)
Other partners > University of Strathclyde (UNITED KINGDOM)
Laboratory name:
Agence nationale de la Recherche
Deposited On:13 Feb 2019 14:55

Repository Staff Only: item control page