学海网 文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Nested-dissection orderings for sparse LU with partial pivoting

Nested-dissection orderings for sparse LU with partial pivoting

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

第1页

TOP相关主题

  • partial pivoting
  • partial ordering
  • pivoting
  • pivoting insert
  • pivoting 矩阵
  • pivoting strategy
  • complete pivoting
  • aortic dissection

我要评论

相关文档

  • ...IN LU DECOMPOSITION WITH PARTIAL PIVOTING_免费下...

    Nested-dissection orderi... 暂无评价 8页 免费 Efficient sparse LU fact.... LOCALITY OF REFERENCE IN LU DECOMPOSITION WITH PARTIAL PIVOTING SIVAN TOLEDO...

  • Partial Orderings

    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. ...

  • A nested dissection approach

    4) Sum: Sum up the partial y values. The matrix and vector partitioning... to the well-known nested dissection method for sparse matrix ordering. ...

  • Bibliography

    Fonlupt, and V. Klee. Helly’s theorem and ...Nested dissection of a regular ?nite element mesh...G. Lewis. Orderings for parallel sparse symmetric...

  • Summary of available software for sparse direct met...

    nested or one-way dissection (including all graph-based partitionings), ...Yang. E?cient sparse LU factorization with partial pivoting on distributed ...

  • ...Math) Computational Methods for Large Sparse Sys...

    Direct Methods for Sparse Matrices, I.S. Du?,...Numerical pivoting. Partial solutions. Experiments ...Nested dissection. Cliques and clique trees. ...

  • ...Math) Computational Methods for Large Sparse Sys...

    Direct Methods for Sparse Matrices, I.S. Du?,...Numerical pivoting. Partial solutions. Experiments ...Nested dissection. Cliques and clique trees. ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
新浪认证  诚信网站  绿色网站  可信网站   非经营性网站备案
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.xuehai.net All Rights Reserved.  email
返回顶部