On the design of interfaces to sparse direct solvers

Abstract

We discuss the design of general, flexible, consistent, reusable, and efficient interfaces to software libraries for the direct solution of systems of linear equations on both serial and distributed memory architectures. We introduce a set of abstract classes to access the linear system matrix elements and their distribution, access vector elements, and control the solution of the linear system.

We describe a concrete implementation of the proposed interfaces, and report examples of applications and numerical results showing that the overhead induced by the object-oriented design is negligible under typical conditions of usage. We include examples of applications, and we comment on the advantages and limitations of the design.

References

1. Alexandrescu, A. 2001. Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley Longman Publishing Co., Inc., Boston, MA.
2. Alpatov, P., Baker, G., Edwards, C., Gunnels, J., Morrow, G., Overfelt, J., van de Geijn, R., and Wu, Y.-J. J. 1997. Plapack: parallel linear algebra package design overview. In Supercomputing '97: Proceedings of the 1997 ACM/IEEE Conference on Supercomputing (CDROM). ACM Press, New York, NY. 1--16.
3. Amestoy, P., Duff, I., L'Excellent, J.-Y., and Koster, J. 2003. MUltifrontal Massively Parallel Solver (MUMPS Versions 4.3.1) Users' Guide. CERFACS, Toulouse, France.
4. Amestoy, P. R., Davis, T. A., and Duff, I. S. 2004. Algorithm 837: AMD, an approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 3, 381--388.
5. Amestoy, P. R., Duff, I. S., L'excellent, J.-Y., and Li, X. S. 2001. Analysis and comparison of two general sparse solvers for distributed memory computers. ACM Trans. Math. Softw. 27, 4, 388--421.
6. Anderson, E., Bai, Z., Bischof, C., Blackford, L. S., Demmel, J., Dongarra, J. J., Croz, J. D., Hammarling, S., Greenbaum, A., McKenney, A., and Sorensen, D. 1999. LAPACK Users' Guide, third ed. Society for Industrial and Applied Mathematics, Philadelphia, PA.
7. Balay, S., Buschelman, K., Eijkhout, V., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H. 2004. PETSc Users Manual. Tech. rep. ANL-95/11---Revision 2.1.5, Argonne National Laboratory.
8. Baumann, M., Fleischmann, P., and Mutzbauer, O. 2003. Double ordering and fill-in for the LU factorization. SIAM J. Matrix Anal. Appl. 25, 3, 630--641.
9. Beazley, D. M. 2003. Automated scientific software scripting with SWIG. Future Gener. Comput. Syst. 19, 5, 599--609.
10. Blackford, L. S., Choi, J., Cleary, A., D'Azevedo, E., Jemmel, J., Dhillon, I., Dongarra, J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., alker, D. W., and Whaley, R. C. 1997. ScaLAPACK Users' Guide. SIAM Pub.
11. Boisvert, R. F., Pozo, R., Remington, K., Barrett, R. F., and Dongarra, J. J. 1997. Matrix market: a Web resource for test matrix collections. In Proceedings of the IFIP TC2/WG2.5 Working Conference on Quality of Numerical Software. Chapman & Hall, Ltd., London, UK. 125--137.
12. Brandt, A. 1977. Multi-level adaptive solutions to boundary-value problems. Math. Comp. 31, 333--390.
13. Davis, T. A. 2003. UMFPACK home page. http://www.cise.ufl.edu/research/sparse/umfpack.
14. Davis, T. A. 2004. A column pre-ordering strategy for the unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30, 2, 165--195.
15. Davis, T. A. 2006. Direct methods for sparse linear systems. http://www.siam.org/fa02.
16. Davis, T. A. and Palamadai, E. 2005. KLU: a sparse LU factorization for circuit simulation matrices. Tech. rep., Univ. of Florida.
17. Daydé, M., Giraud, L., Hernandez, M., L'Excellent, J.-Y., Puglisi, C., and Pantel, M. 2004. An Overview of the GRID-TLSE Project. In Poster Session of the 6th International Conference on Vectorand Parallel Processing (VECPAR'04). Valencia, Spain. 851--856.
18. Demmel, J. W., Gilbert, J. R., and Li, X. S. 2003. SuperLU Users' Guide. Computer Science Division, University of California, Berkely.
19. Dobrian, F., Kumfert, G., and Pothen, A. 1999. The design of sparse direct solvers using object-oriented techniques. Tech. rep., Institute for Computer Applications in Science and Engineering (ICASE), Hampton, Virginia.
20. Dongarra, J. J., Duff, I. S., Sorensen, D. C., and van der Vorst, H. 1998. Numerical Linear Algebra for High-Performance Computing. SIAM, Philadelphia, PA.
21. Duff, I. S. 1997. Sparse numerical linear algebra: direct methods and preconditioning. In The State of the art in Numerical Analysis, I. S. Duff and G. A. Watson, Eds. Oxford University Press, Oxford. 27--62.
22. Duff, I. S., Erisman, A. M., and Reid, J. K. 1986. Direct Methods for Sparse Matrices. Oxford University Press, Inc., New York, NY, USA.
23. Duff, I. S., Grimes, R. G., and Lewis, J. G. 1989. Sparse matrix test problems. ACM Trans. Math. Softw. 15, 1, 1--14.
24. Duff, I. S., Heroux, M. A., and Pozo, R. 2002. An overview of the sparse basic linear algebra subprograms: The new standard from the BLAS technical forum. ACM Trans. Math. Softw. 28, 2, 239--267.
25. Duff, I. S. and Reid, J. K. 1979. Performance evaluation of codes for sparse matrix problems. In Performance Evaluation of Numerical Software. North-Holland, New York. 121--135.
26. Falgout, R. D. and Yang, U. M. 2002. HYPRE: A library of high performance preconditioners. Lect. Notes Comput. Sci. 2331, 632--641.
27. Farhat, C. and Roux, F.-X. 1992. An unconventional domain decomposition method for an efficient parallel solution of large-scale finite element systems. SIAM J. Sci. Stat. Comput. 13, 1, 379--396.
28. Free Software Foundation. 2004a. Autoconf Home Page. http://www.gnu.org/software/autoconf.
29. Free Software Foundation. 2004b. Automake Home Page. http://www.gnu.org/software/automake.
30. Freeman, E., Bates, B., and Sierra, K. 2004. Head First Design Patterns. O'Reilly.
31. Gamma, E., Helm, R., Johnson, R., and Vlissides, J. 1995. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
32. George, A. and Liu, J. 1999. An object-oriented approach to the design of a user interface for a sparse matrix package. SIAM J. Matrix Anal. Appl. 20, 4, 953--969.
33. George, A. and Liu, J. W. H. 1979. The design of a user interface for a sparse matrix package. ACM Trans. Math. Softw. 5, 2, 139--162.
34. Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations 3rd ed. Johns Hopkins University Press, Baltimore, MD, USA.
35. Gould, N., Hu, Y., and Scott, J. 2007. A numerical evaluation of sparse direct solvers for the solution of large, sparse, symmetric linear systems of equations. ACM Trans. Math. Softw. 33. 2, Art 10.
36. Gropp, W., Huss-Lederman, S., Lumsdaine, A., Lusk, E., Nitzberg, B., Saphir, W., and Snir, M. 1998. MPI---The Complete Reference: Volume 2, The MPI-2 Extensions. MIT Press, Cambridge, MA, USA.
37. Gupta, A. 2001. Recent advances in direct methods for solving unsymmetric sparse systems of linear equations. Technical Report, IBM T.J. Watson Research Center.
38. Hackbusch, W. 1985. Multi-grid Methods and Applications. Springer-Verlag, Berlin.
39. Heroux, M. A. 2002. Epetra Reference Manual, 2.0 ed. http://software.sandia.gov/trilinos/packages/epetra/doxygen/latex/EpetraReferenceManual.pdf.
40. Heroux, M. A., Bartlett, R. A., Howle, V. E., Hoekstra, R. J., Hu, J. J., Kolda, T. G., Lehoucq, R. B., Long, K. R., Pawlowski, R. P., Phipps, E. T., Salinger, A. G., Thornquist, H. K., Tuminaro, R. S., Willenbring, J. M., Williams, A., and Stanley, K. S. 2005. An overview of the trilinos project. ACM Trans. Math. Softw. 31, 3, 397--423.
41. Irony, D., Shklarski, G., and Toledo, S. 2004. Parallel and fully recursive multifrontal supernodal sparse cholesky. Future Gen. Comput. Sys. 20, 3 (Apr.), 425--440.
42. Li, X. S. and Demmel, J. W. 1998. Making sparse Gaussian elimination scalable by static pivoting. In Supercomputing '98: Proceedings of the 1998 ACM/IEEE Conference on Supercomputing (CDROM). IEEE Computer Society, Washington, DC. 1--17.
43. Luján, M., Freeman, T. L., and Gurd, J. R. 2000. Oolala: an object oriented analysis and design of numerical linear algebra. In OOPSLA '00: Proceedings of the 15th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM Press, New York, NY. 229--252.
44. Malard, J. 1991. Threshold pivoting for dense lu factorization on distributed memory multiprocessors. In Supercomputing '91: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing. ACM Press, New York, NY. 600--607.
45. Quarteroni, A. and Valli, A. 1999. Domain Decomposition Methods for Partial Differential Equations. Oxford University Press, Oxford.
46. Raghavan, P. 2002. Domain-separator codes for the parallel solution of sparse linear systems. Tech. rep. CSE-02-004, Department of Computer Science and Engineering, The Pennsylvania State University.
47. Rotkin, V. and Toledo, S. 2004. The design and implementation of a new out-of-core sparse Cholesky factorization method. ACM Trans. Math. Softw. 30, 19--46.
48. Rozin, E. and Toledo, S. 2005. Locality of reference in sparse Cholesky methods. Electronic Trans. Numerical Anal. 21, 81--106.
49. Saad, Y. 1996. Iterative Methods for Sparse Linear Systems. PWS, Boston.
50. Sala, M. 2004. Amesos 2.0 reference guide. Tech. Rep. SAND-4820, Sandia National Laboratories, Albuquerque, NM. September.
51. Sala, M. 2005. Distributed sparse linear algebra with PyTrilinos. Tech. Rep. SAND2005-3835, Sandia National Laboratories, Albuquerque NM. June.
52. Sala, M. and Heroux, M. 2005. Robust algebraic preconditioners with IFPACK 3.0. Tech. Rep. SAND-0662, Sandia National Laboratories, Albuquerque, NM. February.
53. Sala, M., Heroux, M. A., and Day, D. 2004. Trilinos Tutorial, 4.0 ed.
54. Sala, M., Hu, J., and Tuminaro, R. 2004. ML 3.1 smoothed aggregation user's guide. Tech. Rep. SAND-4819, Sandia National Laboratories. September.
55. Sala, M., Spotz, W. F., and Heroux, M. A. 2005. PyTrilinos: High-performance distributed-memory solvers for Python. Submitted.
56. Sala, M., Stanley, K. S., Heroux, M. A., and Hoekstra, R. 2006. Amesos home page. http://software.sandia.gov/trilinos/packages/amesos, Sandia National Laboratories, Albuquerque, NM.
57. Schenk, O. and Gärtner, K. 2004a. On fast factorization pivoting methods for sparse symmetric indefinite systems. Tech. Rep. Department of Computer Science, University of Basel.
58. Schenk, O. and Gärtner, K. 2004b. Solving unsymmetric sparse systems of linear equations with PARDISO. J. Future Gen. Comput. Sys. 20, 3, 475--487.
59. Smith, B., Bjorstad, P., and Gropp, W. 1996. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press.
60. Stroustrup, B. 1986. The C++ Programming Language. Addison-Wesley, Reading, MA.
61. Teuchos 2006. Teuchos Home Page. http://software.sandia.gov/trilinos/packages/teuchos.
62. The Mozilla Organization. 2004. Mozilla Bugzilla Home Page. http://www.mozilla.org/projects/bugzilla.
63. Wise, G. B. 1996. An overview of the standard template library. SIGPLAN Not. 31, 4, 4--10.

Index Terms

• Computing methodologies

  • Parallel computing methodologies

    • Parallel programming languages

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

      • Linear algebra algorithms

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Computations on matrices

• Software and its engineering

  • Software creation and management

    • Software development techniques

      • Object oriented development

  • Software notations and tools

    • Development frameworks and environments

      • Object oriented frameworks

    • General programming languages

      • Language types

        • Parallel programming languages

    • Software libraries and repositories