The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/34119
Record Status Checked
Record Id 34119
Title Reducing the total bandwidth of a sparse unsymmetric matrix
Abstract For a sparse symmetric matrix, there has been much attention given to algorithms for reducing the bandwidth. As far as we can see, little has been done for the unsymmetric matrix A, which has distinct lower and upper bandwidths l and u. When Gaussian elimination with row interchanges is applied, the lower bandwidth is unaltered while the upper bandwidth becomes l + u. With column interchanges, the upper bandwidth is unaltered while the lower bandwidth becomes l+u. We therefore seek to reduce min(l; u) + l + u, which we call the total bandwidth. We consider applying the reverse Cuthill-McKee algorithm to A+AT , to the row graph of A, and to the bipartite graph of A. We also propose a variation that may be applied directly to A. When solving linear systems, if the matrix is preordered to block triangular form, it suffices to apply the band-reducing method to the blocks on the diagonal. We have found that this is very beneficial on matrices from actual applications. Finally, we have adapted the node-centroid and hill-climbing ideas of Lim, Rodrigues and Xiao to the unsymmetric case and found that these give further worthwhile gains. Numerical results for a range of practical problems are presented and comparisons made with other possibilities, including the recent lexicographical method of Baumann, Fleishmann and Mutzbauer.
Organisation CCLRC , CSE , CSE-NAG
Keywords Gaussian elimination , matrix bandwidth , sparse unsymmetric matrices
Funding Information
Related Research Object(s):
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Report RAL Technical Reports RAL-TR-2005-001. 2005. raltr-2005001.pdf 2005
Journal Article SIAM J Matrix Anal A 28 (2005): 805-821. 2005