Copyright © (2002) by Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit or commericial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.
During the past few years, algorithmic improvements alone have reduced the time required for the direct solution of unsymmetric sparse systems of linear equations by almost an order of magnitude. This paper compares the performance of some state-of-the-art software packages for solving general sparse systems. In particular. it demonstrates the consistently high level of performance achieved by WSMP-the most recent of such solvers. It compares the various algorithmic components of these solvers and shows that the choices made in WSMP enable it to run more than twice as fast as the best amongst other similar solvers. The key features of WSMP that contribute to its performance include a prepermutation of rows to place large entries on the diagonal. a symmetric fill-reducing permutation based on the nested dissection ordering algorithm, and an unsymmetric-pattern multifrontal factorization guided by a minimal task-dependency graph with symmetric inter-supernode threshold pivoting. Our experiments show that WSMP can factor some of the largest sparse matrices available from real applications in only a few seconds on a-CPU workstation.
By: Anshul Gupta
Published in: ACM Transactions on Mathematical Software , volume 28, (no 3), pages 301-24 in 2002
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .