Abstract. We describe the implementation and performance of a novel fill-minimization ordering technique for sparse LU factorization with partial pivoting. The technique was proposed by Gilbert and Schreiber in 1980 but never implemented and tested. Like o
NESTED-DISSECTIONORDERINGSFORSPARSELU
WITHPARTIALPIVOTING
IGORBRAINMANANDSIVANTOLEDO
Abstract.Wedescribetheimplementationandperformanceofanovel ll-minimizationorderingtechniqueforsparseLUfactoriza-tionwithpartialpivoting.ThetechniquewasproposedbyGilbertandSchreiberin1980butneverimplementedandtested.LikeothertechniquesfororderingsparsematricesforLUwithpartialpivoting,ournewmethodpreordersthecolumnsofthematrix(therowpermutationischosenbythepivotingsequenceduringthenumericalfactorization).Alsolikeothermethods,thecolumnpermutationQthatweselectisapermutationthatminimizesthe llintheCholeskyfactorofQTATAQ.Unlikeexistingcolumn-orderingtechniques,whichallrelyonminimum-degreeheuristics,ournewmethodisbasedonanested-dissectionorderingofATA.Ouralgorithm,however,nevercomputesarepresentationofATA,whichcanbeexpensive.WeonlyworkwitharepresentationofAitself.Ourexperimentsdemonstratethatthemethodise cientandthatitcanreduce llsigni cantlyrelativetothebestexistingmethods.ThemethodreducestheLUrunningtimeonsomeverylargematrices(tensofmillionsofnonzerosinthefactors)bymorethanafactorof2.
1.Introduction
Reorderingthecolumnsofsparsenonsymmetricmatricescansig-ni cantlyreduce llinsparseLUfactorizationswithpartialpivot-ing.Reducing llinafactorizationreducestheamountofmemoryrequiredtostorethefactors,theamountofworkinthefactorization,andtheamountofworkinsubsequenttriangularsolves.Symmet-ricpositive-de nitematrices,whichcanbefactoredwithoutpivoting,arenormallyreorderedtoreduce llbyapplyingthesamepermuta-tiontoboththerowsandcolumnsofthematrix.Applyingthesamepermutationtotherowsandcolumnspreservesthesymmetryofthematrix.Whenpartialpivotingisrequiredformaintainingnumericalstability,however,prepermutingtherowsismeaningless,sincetherows
ThisresearchwassupportedbyIsraelScienceFoundationfoundedbytheIsraelAcademyofSciencesandHumanities(grantnumber572/00andgrantnumber9060/99)andbytheUniversityResearchFundofTel-AvivUniversity.
1
Nested-dissection orderi... 暂无评价 8页 免费 Efficient sparse LU fact.... LOCALITY OF REFERENCE IN LU DECOMPOSITION WITH PARTIAL PIVOTING SIVAN TOLEDO...
17页 免费 Nested-dissection orderi... 暂无评价 8页 免费 Partial orderings of eve... 暂无评价 19页 免费 elimination orderings 暂无评价 15页 免费喜欢...
LAPACK’s “dgesv_”: full LU decomposition with partial pivoting and row interchanges ? Intel Pardiso: Parallel Direct Sparse Solver. Multifront method. ...
LAPACK’s “dgesv_”: full LU decomposition with partial pivoting and row interchanges ? Intel Pardiso: Parallel Direct Sparse Solver. Multifront method. ...
LAPACK’s “dgesv_”: full LU decomposition with partial pivoting and row interchanges ? Intel Pardiso: Parallel Direct Sparse Solver. Multifront method. ...
4) Sum: Sum up the partial y values. The matrix and vector partitioning... to the well-known nested dissection method for sparse matrix ordering. ...
Fonlupt, and V. Klee. Helly’s theorem and ...Nested dissection of a regular ?nite element mesh...G. Lewis. Orderings for parallel sparse symmetric...
nested or one-way dissection (including all graph-based partitionings), ...Yang. E?cient sparse LU factorization with partial pivoting on distributed ...
Direct Methods for Sparse Matrices, I.S. Du?,...Numerical pivoting. Partial solutions. Experiments ...Nested dissection. Cliques and clique trees. ...
Direct Methods for Sparse Matrices, I.S. Du?,...Numerical pivoting. Partial solutions. Experiments ...Nested dissection. Cliques and clique trees. ...
我要评论