A symmetry preserving algorithm for matrix scaling

Philip Knight, Daniel Ruiz, Bora Ucar

Research output: Contribution to journalArticle

13 Citations (Scopus)
165 Downloads (Pure)

Abstract

We present an iterative algorithm which asymptotically scales the $\infty$-norm of each row and each column of a matrix to one. This scaling algorithm preserves symmetry of the original matrix and shows fast linear convergence with an asymptotic rate of 1/2. We discuss extensions of the algorithm to the 1-norm, and by inference to other norms. For the 1-norm case, we show again that convergence is linear, with the rate dependent on the spectrum of the scaled matrix. We demonstrate experimentally that the scaling algorithm improves the conditioning of the matrix and that it helps direct solvers by reducing the need for pivoting. In particular, for symmetric matrices the theoretical and experimental results highlight the potential of the proposed algorithm over existing alternatives.
Original languageEnglish
Pages (from-to)931–955
Number of pages25
JournalSIAM Journal on Matrix Analysis and Applications
Volume35
Issue number3
Early online date17 Jul 2014
DOIs
Publication statusPublished - 2014

Fingerprint

Scaling
Norm
Symmetry
Linear Convergence
Pivoting
Symmetric matrix
Conditioning
Iterative Algorithm
Dependent
Alternatives
Experimental Results
Demonstrate

Keywords

  • sparse matrices
  • equilibration
  • matrix scaling

Cite this

Knight, Philip ; Ruiz, Daniel ; Ucar, Bora. / A symmetry preserving algorithm for matrix scaling. In: SIAM Journal on Matrix Analysis and Applications. 2014 ; Vol. 35, No. 3. pp. 931–955.
@article{0e12e3e410214c4db52da252c20ebb8e,
title = "A symmetry preserving algorithm for matrix scaling",
abstract = "We present an iterative algorithm which asymptotically scales the $\infty$-norm of each row and each column of a matrix to one. This scaling algorithm preserves symmetry of the original matrix and shows fast linear convergence with an asymptotic rate of 1/2. We discuss extensions of the algorithm to the 1-norm, and by inference to other norms. For the 1-norm case, we show again that convergence is linear, with the rate dependent on the spectrum of the scaled matrix. We demonstrate experimentally that the scaling algorithm improves the conditioning of the matrix and that it helps direct solvers by reducing the need for pivoting. In particular, for symmetric matrices the theoretical and experimental results highlight the potential of the proposed algorithm over existing alternatives.",
keywords = "sparse matrices, equilibration, matrix scaling",
author = "Philip Knight and Daniel Ruiz and Bora Ucar",
year = "2014",
doi = "10.1137/110825753",
language = "English",
volume = "35",
pages = "931–955",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
number = "3",

}

A symmetry preserving algorithm for matrix scaling. / Knight, Philip; Ruiz, Daniel; Ucar, Bora.

In: SIAM Journal on Matrix Analysis and Applications, Vol. 35, No. 3, 2014, p. 931–955.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A symmetry preserving algorithm for matrix scaling

AU - Knight, Philip

AU - Ruiz, Daniel

AU - Ucar, Bora

PY - 2014

Y1 - 2014

N2 - We present an iterative algorithm which asymptotically scales the $\infty$-norm of each row and each column of a matrix to one. This scaling algorithm preserves symmetry of the original matrix and shows fast linear convergence with an asymptotic rate of 1/2. We discuss extensions of the algorithm to the 1-norm, and by inference to other norms. For the 1-norm case, we show again that convergence is linear, with the rate dependent on the spectrum of the scaled matrix. We demonstrate experimentally that the scaling algorithm improves the conditioning of the matrix and that it helps direct solvers by reducing the need for pivoting. In particular, for symmetric matrices the theoretical and experimental results highlight the potential of the proposed algorithm over existing alternatives.

AB - We present an iterative algorithm which asymptotically scales the $\infty$-norm of each row and each column of a matrix to one. This scaling algorithm preserves symmetry of the original matrix and shows fast linear convergence with an asymptotic rate of 1/2. We discuss extensions of the algorithm to the 1-norm, and by inference to other norms. For the 1-norm case, we show again that convergence is linear, with the rate dependent on the spectrum of the scaled matrix. We demonstrate experimentally that the scaling algorithm improves the conditioning of the matrix and that it helps direct solvers by reducing the need for pivoting. In particular, for symmetric matrices the theoretical and experimental results highlight the potential of the proposed algorithm over existing alternatives.

KW - sparse matrices

KW - equilibration

KW - matrix scaling

UR - http://epubs.siam.org/loi/sjmael

U2 - 10.1137/110825753

DO - 10.1137/110825753

M3 - Article

VL - 35

SP - 931

EP - 955

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 3

ER -