PSBLAS: a library for parallel linear algebra computation on sparse matrices

ABSTRACT

Many computationally intensive problems in engineering and science give rise to the solution of large, sparse, linear systems of equations. Fast and efficient methods for their soltion are very important because these systems usually occur in the innermost loop of the computational scheme. Parallelization is often necessary to achieve an acceptable level of performance. This paper presents the design, implementation, and interface of a library of Basic Linear Algebra Subroutines for sparse matrices (PSBLAS) which is specifically tailored to distributed-memory computers. PSBLAS enables easy, efficient, and portable implementations of parallel iterative solvers for linear systems. The interface keeps in view a Single Program Multiple Data programming model on distributed-memory machines. However, the architecture of the library does not exclude an implementation in different paradigms, such as those based on the shared-memory model.

REFERENCES

• 1: Mario Arioli , Iain Duff , Daniel Ruiz, Stopping criteria for iterative solvers, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.138-144, Jan. 1992 [doi>10.1137/0613012]
• 2: BALAY, S., GROPP, W., MCINNES,L.C.,AND SMITH, B. 1995. PETSc 2.0 user manual. ANL-95/11 - Revision 2.0.22. Argonne National Laboratory, Argonne, IL.
• 3: BARRETT, R., BERRY, M., CHAN, T., DEMMEL, J., DONAT, J., DONGARRA, J., EIJKHOUT, V., POZO, R., ROMINE, C., AND VORST,H.V. D. 1994. Templates for the Solution of Linear Systems. SIAM, Philadelphia, PA.
• 4: Are Magnus Bruaset , Hans Petter Langtangen, Object-oriented design of preconditioned iterative methods in diffpack, ACM Transactions on Mathematical Software (TOMS), v.23 n.1, p.50-80, March 1997 [doi>10.1145/244768.244776]
• 5: CARNEY, S., HEROUX,M.A.,LI, G., AND WU, K. 1994. A revised proposal for a sparse BLAS toolkit. Tech. Rep. 94-034. Army High Performance Computing Research Center, Minneapolis, MN.
• 6: CERIONI, F., COLAJANNI, M., FILIPPONE, S., AND MAIOLATESI, S. 1996. PSBLAS user's guide. RI.96.11 (April). Univ. of Rome-Tor Vergata, Rome, Italy.
• 7: Jaeyoung Choi , James Demmel , I. Dhillon , Jack Dongarra , Susan Ostrouchov , Antoine Petitet , Ken Stanley , David W. Walker , R. Clinton Whaley, ScaLAPACK: A Portable Linear Algebra Library for Distributed Memory Computers - Design Issues and Performance, Proceedings of the Second International Workshop on Applied Parallel Computing, Computations in Physics, Chemistry and Engineering Science, p.95-106, August 21-24, 1995
• 8: Jack J. Dongarra , R. C Whaley, LAPACK Working Note 94: A User''s Guide to the BLACS v1.0, University of Tennessee, Knoxville, TN, 1995
• 9: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 10: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 11: Iain S. Duff , Michele Marrone , Giuseppe Radicati , Carlo Vittoli, Level 3 basic linear algebra subprograms for sparse matrices: a user-level interface, ACM Transactions on Mathematical Software (TOMS), v.23 n.3, p.379-401, Sept. 1997 [doi>10.1145/275323.275327]
• 12: Salvatore Filippone , Michele Colajanni , Dario Pascucci, An Object-Oriented Environment for Sparse Parallel Computation on Adaptive Grids, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.365, April 12-16, 1999
• 13: FILIPPONE, S., MARRONE, M., AND RADICATI DI BROZOLO, G. 1992. Parallel preconditioned conjugate-gradient type algorithms for general sparsity structures. Inter. J. Comput. Math. 40, 159-167.
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Anne Greenbaum, Iterative methods for solving linear systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 16: Bruce Hendrickson , Robert Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM Journal on Scientific Computing, v.16 n.2, p.452-469, March 1995 [doi>10.1137/0916028]
• 17: HUTCHINSON, S., PREVOST, L., SHADID, J., TONG, C., AND TUMINARO, R. 1998. Aztec user's guide: Version 2.0. Sandia National Laboratories, Livermore, CA.
• 18: KARYPIS,G.AND KUMAR, V. 1995. METIS: Unstructured graph partitioning and sparse matrix ordering system. Computer Science Department, Univ. of Minnesota, Minneapolis, MN. http://www.cs.umn.edu/ karypis
• 19: KELLEY, C. T. 1995. Iterative Methods for Linear and Nonlinear Equations. SIAM Frontiers in Applied Mathematics Series. SIAM, Philadelphia, PA.
• 20: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 21: L. Machiels , M. O. Deville, Fortran 90: an entry to object-oriented programming for the solution of partial differential equations, ACM Transactions on Mathematical Software (TOMS), v.23 n.1, p.32-49, March 1997 [doi>10.1145/244768.244774]
• 22: Michael Metcalf , John Reid, Fortran 90 explained, Oxford University Press, Inc., New York, NY, 1990
• 23: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

General Terms:
Algorithms, Design

Keywords:
basic linear algebra subprograms