Premium
On equilibration and sparse factorization of matrices arising in finite element solutions of partial differential equations
Author(s) -
de Almeida Valmor F.,
Chapman Andrew M.,
Derby Jeffrey J.
Publication year - 2000
Publication title -
numerical methods for partial differential equations
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.901
H-Index - 61
eISSN - 1098-2426
pISSN - 0749-159X
DOI - 10.1002/(sici)1098-2426(200001)16:1<11::aid-num2>3.0.co;2-x
Subject(s) - scaling , factorization , norm (philosophy) , mathematics , basis (linear algebra) , finite element method , stability (learning theory) , partial differential equation , element (criminal law) , algebra over a field , algorithm , computer science , mathematical optimization , pure mathematics , mathematical analysis , geometry , machine learning , physics , political science , law , thermodynamics
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. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 11–29, 2000