On equilibration and sparse factorization of matrices arising in finite element solutions of partial differential equations

Valmor F. De Almeida, Andrew M. Chapman, Jeffrey J. Derby

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Investigations of scaling and equilibration of general matrices have been traditionally aimed at the effects on the stability and accuracy of LU factorizations - the so-called scaling problem. Notably, Skeel (1979) concludes that no systematic scaling procedure can be concocted for general matrices exempt from the danger of disastrous effects. Other researchers suggest that scaling procedures are not beneficial and should be abandoned altogether. Stability and accuracy issues notwithstanding, we show that this unglamorous technique has a profound impact on the sparsity of the resulting LU factors. In the modern era of fast computing, equilibration can play a key role in constructing incomplete sparse factorizations to solve a problem unstably, but quickly and iteratively. This article presents practical evidence, on the basis of sparsity, that scaling is an indispensable companion for sparse factorization algorithms when applied to realistic problems of industrial interest. In light of our findings, we conclude that equilibration with the ∞-norm is superior than equilibration with the 2-norm.

Original languageEnglish (US)
Pages (from-to)11-29
Number of pages19
JournalNumerical Methods for Partial Differential Equations
Volume16
Issue number1
DOIs
StatePublished - Jan 2000

Keywords

  • Incomplete LUfactorization
  • Incompressible fluids
  • Matrix equilibration
  • Navier-Stokes equations
  • Pivoting
  • Preconditioning
  • Scaling
  • Sparse finite-element matrices

Fingerprint Dive into the research topics of 'On equilibration and sparse factorization of matrices arising in finite element solutions of partial differential equations'. Together they form a unique fingerprint.

Cite this