Volume 14 Number 3	July 1998

In Vivo Deployment of Palmaz-Schatz Stent Sparse Matrix Methods Fluid Phase Equilibria Modeling the Dynamics of RNA Seminar Synopsis Visitors Research Reports umerical linear algebra is at the heart of the solution methods used for handling a large number of scientific and engineering applications. The majority of problems encountered in these applications involve linear systems or eigenvalue problems with very large sparse matrices. A sparse matrix is one with very few nonzero elements. As a typical example, consider a linear system consisting of two hundred thousand equations. Each equation involves forty unknowns on average. The resulting matrix will have forty nonzero elements per row giving a total of eight million nonzero entries for the matrix. This is by no means a large problem by the standard of current large scale applications. An excellent example of the potential complexity of these problems is provided by the Accelerated Strategic Computing Initiative (ASCI), which the Department of Energy (DOE) has launched in the last few years. The goal of ASCI is to replace nuclear testing by accurate numerical simulations that handle complex physical phenomena. Pattern of a nine-point finite difference matrix Anticipation is that problems of sizes reaching hundreds of millions to billions will be routinely solved in ASCI simulations using a number of massively parallel computers at DOE labs. Sparse matrix problems require special techniques which avoid or reduce the storage of zero elements and work only with the nonzero entries. Professor Yousef Saad’s research team in the Computer Science and Engineering Department at the University of Minnesota is working on such techniques. Two types of problems are tackled. Pattern of a nine-point matrix shown above after a multi-color reordering The first problem is concerned with the solution of large sparse eigenvalue problems which arise in electronic structures calculations. This is being worked on by Professor Saad and Dr. Thierry Braconnier as well as Professor James Chelikowsky and Dr. Serdar Ogut of the Chemical Engineering and Materials Science Department at the University of Minnesota. The recent bulletin article by Professor James Chelikowsky describes this problem in detail (Volume 14 Number 1, Fall 1997). The second type of problem is that of solving large sparse linear systems. One of the main goals of this second research theme is to develop parallel iterative solution methods that are at the same time robust and efficient. For small problems, direct solution methods (e.g., Gaussian elimination) are usually preferred because of their reliability. However, direct methods are not feasible for large problems such as the ones mentioned above because of their very high memory requirements. It should be noted that memory rather than computational cost is the primary limitation of direct methods. Pattern of the matrix SAYLR4 from the Harewell-Boeing collection Standard iterative methods usually consist of an accelerator (Conjugate Gradient, GMRES, . . . ) and a preconditioner. Often, the accelerator is an optimal process which obtains the best iterate from a dynamically constructed subspace of approximations. Preconditioning is a process that helps the accelerator in some ways by transforming the original problem into one that easier to solve. Structure of the BILUM preconditioning matrix associated with the matrix SAYLR4 from the Harwell-Boeing collection of matrices. Ten levels of reduction are applied Thus, the linear system is transformed so the accelerator is likely to converge faster. SPARSKIT is a widely used package that provides a number of accelerators and preconditioners. Though this package has been developed for sequential computers, a parallel version of its solvers is now available in a package called PSPARSLIB. One method that has been considered by Professor Saad and Jun Zhang of the Computer Science and Engineering Department is illustrated in the first figure. The original system is reordered to have the block form shown in the figure. Each large diagonal block is itself a block diagonal matrix. This reordering is obtained by using a succession of Schur complement reductions associated with an independent set reordering by blocks. Variants of this method are similar to multilevel methods and domain decomposition techniques. When the blocks become larger, the method is more akin to a domain decomposition approach. When they are very small (e.g., one or two), then a multigrid like approach results. This class of methods bridges the gap between these two efficient algorithms and has an excellent potential for solving very large systems because of their attractive scalability properties.   HOME | BULLETINS | CONTACT US | PREVIOUS ARTICLE | NEXT ARTICLE | THIS ISSUE   This information is available in alternative formats upon request by individuals with disabilities. Please send email to alt-format@msi.umn.edu or call 612-624-0528.   URL: http:// This page last modified on   Website related questions or problems should be directed to webmaster@msi.umn.edu The Supercomputing Institute does not collect personal information on visitors to our website. For the University of Minnesota policy, see www.privacy.umn.edu.