The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/40495
Record Status Checked
Record Id 40495
Title Ordering techniques for singly bordered block diagonal forms for unsymmetric parallel sparse direct solvers
Abstract The solution of large sparse linear systems of equations is one of the cornerstones of scientific computation. In many applications it is important to be able to solve these systems as rapidly as possible. One approach for very large problems is to reorder the system matrix to bordered block diagonal form and then to solve the block system in parallel. In this paper, we consider the problem of efficiently ordering unsymmetric systems to singly ordered block diagonal form. Algorithims such as the MONET algorithm of Hu, Maguire and Blake (2000) that depend upon computing a representation of AA(superscript T) can be prohibitively expensive when a single (or small number of) matrix factorizations are required. We therefore work with the graph of A(superscript T)+A (orB+B(superscript T, where B is a row permutation of A) and propose new re-ordering algorithms that use only vertex separators and wide separators of this graph. Numerical experiments demonstrate that our methods are efficient and can produce bordered forms that are competitive with those obtained using MONET.
Organisation CCLRC , CSE , CSE-NAG
Funding Information
Related Research Object(s): 29793
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Journal Article Num. Lin. Alg. Applics 12 (2005): 877-894. doi:10.1002/nla.427 2005