OoLALA: an object oriented analysis and design of numerical linear algebra

ABSTRACT

In this paper we review the design of a sequential object oriented linear algebra library, OOLALA. Several designs are proposed and used to classify existing sequential object oriented libraries. The classification is based on the way that matrices and matrix operations are represented. OOLALA's representation of matrices is capable of dealing with certain matrix operations that, although mathematically valid, are not handled correctly by existing libraries. OOLALA also enables implementations of matrix calculations at various abstraction levels ranging from the relatively low-level abstraction of a Fortran BLAS-like implementation to higher-level abstractions that hide many implementation details. OOLALA addresses a wide range of numerical linear algebra functionality while the reviewed object oriented libraries concen trate on parts of such functionality. We include some preliminary performance results for a Java implementation of OOLALA.

REFERENCES

• 1: Advanced Computing Laboratory, Los Alamos National Laboratory. Parallel Object-Oriented Methods and Applications (POOMA) framework web page. http://www.acl.lanl.gov/Pooma.
• 2: B. A. Allan, R. L. Clay, K. D. Mish, and A. B. Williams. ISIS++ Reference Guide: Iterative Scalable Implicit Solver in C++ version 1.1. Sandia National Laboratories Livermore, 1999.
• 3: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 4: H. Anton and C. Rorres. Elementary Linear Algebra: Applications Versions. John Wiley & Sons, 7th edition, 1994.
• 5: C. Ashcraft and R. Grimes. SPOOLES: An object-oriented sparse matrix library. InSIAM Conference on Parallel Processing for Scientific Computing, 1999.
• 6: C. Ashcraft and J. W. H. Liu. SMOOTH: A Software Package For Ordering Sparse Matrices, November 1996. Available at http://www.cs.yorku.ca/ joseph/Smooth/SMOOTH.html.
• 7: Satish Balay , William D. Gropp , Lois Curfman McInnes , Barry F. Smith, Efficient management of parallelism in object-oriented numerical software libraries, Modern software tools for scientific computing, Birkhauser Boston Inc., Cambridge, MA, 1997
• 8: S. Balay, W. D. Gropp, L. C. McInnes, and B. F. Smith. PETSc 2.0 users manual. Technical Report ANL-95/11 - Revision 2.0.24, Argonne National Laboratory, 1999.
• 9: R. Barrett, M. Berry, T. Chan, J. Demmel, J. Donato, J. J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, 1994.
• 10: A. J. C. Bik and D. B. Gannon. A note on native level 1 BLAS in Java. Concurrency: Practice and Experience, 9(11):1091-1099, 1997.
• 11: L. Birov, Y. Bartenev, A. Vargin, A. Purkayastha, A. Skjellum, Y. Dandass, and P. Bangalore. The parallel mathematical libraries project (PMLP) - a next generation scalable sparse object oriented mathematical library suite. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, March 1999.
• 12: Lubomir Birov , Arkady Prokofiev , Yuri Bartenev , Anatoly Vargin , Avijit Purkayastha , Yoginder Dandass , Vladimir Erzunov , Elena Shanikova , Anthony Skjellum , Purushotham Bangalore , Eugeny Shuvalov , Vitaly Ovechkin , Nataly Frolova , Sergey Orlov , Sergey Egorov, The Parallel Mathematical Libraries Project (PMLP): Overview, Design Innovations, and Preliminary Results, Proceedings of the 5th International Conference on Parallel Computing Technologies, p.186-193, September 06-10, 1999
• 13: Blitz++ library web page. http://oonumerics.org/blitz/.
• 14: Brian Blount , Siddhartha Chatterjee, An Evaluation of Java for Numerical Computing, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.35-46, December 08-11, 1998
• 15: B. Blount and S. Chatterjee. An evaluation of Java for numerical computing. Scientific Programming, 7(2):97-110, 1999.
• 16: R. F. Boisvert, J. J. Dongarra, R. Pozo, K. A. Remington, and G. W. Stewart. Developing numerical libraries in Java. Concurrency: Practice and Experience, 10(11-13):1117-1129, 1998.
• 17: 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]
• 18: Z. Budimlic and K. Kennedy. The cost of being object-oriented: A preliminary study. Scientific Programming, 7(2):87-96, 1999.
• 19: Z. Budimlic and K. Kennedy. Prospects for scientific computing in polymorphic object-oriented style. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, March 1999.
• 20: Z. Budimlic, K. Kennedy, and J. Piper. The cost of being object-oriented: A preliminary study. In Workshop for Java for High Performance Network Computing at EUROPAR'98, 1998.
• 21: E. Chow and M. A. Heroux. Block preconditioning toolkit reference manual. Technical Report UMSI 96/183, University of Minnesota Supercomputing Institute, September 1996.
• 22: Edmond Chow , Michael A. Heroux, An object-oriented framework for block preconditioning, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.159-183, June 1998 [doi>10.1145/290200.287639]
• 23: Computer Science Department, University of Minnesota and Minnesota Supercomputer Institute, and Mathematical Algorithms and Scalable Computing Group, SGI/Cray Research, Inc. Block Preconditioning ToolKit (BPKIT) web page. http://www.cs.umn.edu/ chow/bpkit.html.
• 24: Department of Computer Science, Rice University. Objects within the Linear Algebra Package (OwlPack) web page. http://www.cs.rice.edu/~budimlic/OwlPack.
• 25: Department of Computer Science, University of Maryland and Mathematical and Computations Sciences Division, NIST. Jampack library web page. ftp://math.nist.gov/pub/Jampack/Jampack.html.
• 26: Department of Computer Science, University of North Carolina. JLAPACK library web page. http://www.cs.unc.edu/Research/HARPOON/jlapack.
• 27: Distributed Applications Research Department, Sandia National Laboratories. Iterative Scalable Implicit Solver in C++ (ISIS++) web page. http://z.ca.sandia.gov/isis.
• 28: Florin Dobrian , Gary Kumfert , Alex Pothen, Object-Oriented Design for Sparse Direct Solvers, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.207-214, December 08-11, 1998
• 29: F. Dobrian, G. Kumfert, and A. Pothen. The design of sparse direct solvers using object-oriented techniques. In A. M. Bruaset, H. P. Langtangen, and E. Quak, editors, Advances in Software Tools for Scientific Computing, volume 10 of Lecture Notes in Computational Science and Engineering. Springer-Verlag, 1999.
• 30: J. Dongarra, A. Lumsdaine, X. Niu, R. Pozo, and K. Remington. Sparse matrix libraries in C++ for high performance architectures. In Proceedings of the Conference on Object Oriented Numerics OON-SKI, pages 122-138, 1994.
• 31: J. Dongarra, A. Lumsdaine, R. Pozo, and K. A. Remington. IML++ v. 1.2: Iterative Methods Library Reference Guide, April 1996. Available at http://math.nist.gov/lapack++/.
• 32: J. Dongarra, R. Pozo, and D. Walker. LAPACK++ v. 1.1: High Performance Linear Algebra Users' Guide, April 1996. Available at http://math.nist.gov/lapack++/.
• 33: J. J. Dongarra , Jermey Du Cruz , Sven Hammerling , I. S. Duff, Algorithm 679; a set of level 3 basic linear algebra subprograms: model implementation and test programs, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.18-28, March 1990 [doi>10.1145/77626.77627]
• 34: 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]
• 35: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, Algorithm 656: an extended set of basic linear algebra subprograms: model implementation and test programs, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.18-32, March 1988 [doi>10.1145/42288.42292]
• 36: 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]
• 37: R. Pozo , J. J. Dongarra , D. W. Walker, LAPACK++: a design overview of object-oriented extensions for high performance linear algebra, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.162-171, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169680]
• 38: J. J. Dongarra, R. Pozo, and D. W. Walker. An object oriented design for high performance linear algebra on distributed memory architectures. In Proceedings of the Conference on Object Oriented Numerics OON-SKI, 1993.
• 39: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 40: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 41: F. R. Gantmacher. The Theory of Matrices Vol. 1. Chelsea, 1959.
• 42: F. R. Gantmacher. The Theory of Matrices Vol. 2. Chelsea, 1959.
• 43: Alan George , Joseph W. H. Liu, The Design of a User Interface for a Sparse Matrix Package, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.139-162, June 1979 [doi>10.1145/355826.355829]
• 44: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 45: Alan George , Joseph Liu, An Object-Oriented Approach to the Design of a User Interface for a Sparse Matrix Package, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.953-969, Oct. 1999 [doi>10.1137/S0895479897317739]
• 46: V. Getov, P. Gray, S. Mintcheva, and V. Sunderam. Multi-language programming environments for high performance Java computing. Scientific Programming, 7(2):139-146, 1999.
• 47: G. H. Golub and C. F. van Loan. Matrix Computations. John Hopkins University Press, 3th edition, 1996.
• 48: Frédéric Guidec , Jean-Marc Jézéquel, Polymorphic Matrices in Paladin, Selected papers from the Workshop, on Object-Based Parallel and Distributed Computation, p.18-37, June 21-23, 1995
• 49: F. Guidec , J.-M. Jézéquel , J.-L. Pacherie, An object-oriented framework for supercomputing, Journal of Systems and Software, v.33 n.3, p.239-251, June 1996 [doi>10.1016/0164-1212(96)00025-8]
• 50: Scott Haney , James Crotinger, How Templates Enable High-Performance Scientific Computing in C++, Computing in Science and Engineering, v.1 n.4, p.66-72, July 1999 [doi>10.1109/5992.774843]
• 51: High Performance Computing Laboratory, Mississippi State University. Parallel Mathematical Library Project (PMLP) web page. http://www.erc.msstate.edu/research/labs/hpcl/pmlp/.
• 52: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996
• 53: Iterative Methods Library (IML++) library web page. http://math.nist.gob/iml++/.
• 54: Java Grande Forum. Making Java Work for High-End Computing, November 1998. Available at http://www.javagrande.org/reports.htm.
• 55: Java Grande Forum. Interim Java Grande Forum Report, June 1999. Available at http://www.javagrande.org/reports.htm.
• 56: Steve Karmesin , James Crotinger , Julian Cummings , Scott Haney , William J. Humphrey , John Reynders , Stephen Smith , Timothy Williams, Array Design and Expression Evaluation in POOMA II, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.231-238, December 08-11, 1998
• 57: Gary Kumfert , Alex Pothen, An Object-Oriented Collection of Minimum Degree Algorithms, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.95-106, December 08-11, 1998
• 58: Laboratory for Scientific Computing, University of Notre Dame. Iterative Template Library (ITL) web page. http://www.lsc.nd.edu/research/itl.
• 59: Laboratory for Scientific Computing, University of Notre Dame. Matrix Template Library (MTL) web page. http://www.lsc.nd.edu/research/mtl.
• 60: LAPACK++ library web page. http://math.nist.gov/lapack++/.
• 61: 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]
• 62: Lie-Quan Lee , Jeremy G. Siek , Andrew Lumsdaine, Generic Graph Algorithms for Sparse Matrix Ordering, Proceedings of the Third International Symposium on Computing in Object-Oriented Parallel Environments, p.120-129, December 08-10, 1999
• 63: Lie-Quan Lee , Jeremy G. Siek , Andrew Lumsdaine, The generic graph component library, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.399-414, November 01-05, 1999, Denver, Colorado, United States
• 64: M. Lee and A. Stepanov. The Standard Template Library. Technical report, Hewlett Packard Laboratories, Menlo Park, California, 1995.
• 65: M. Lujan. Object oriented linear algebra. Master's thesis, Department of Computer Science, University of Manchester, December 1999.
• 66: Nikolay Mateev , Keshav Pingali , Paul Stodghill , Vladimir Kotlyar, Next-generation generic programming and its application to sparse matrix computations, Proceedings of the 14th international conference on Supercomputing, p.88-99, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335240]
• 67: Mathematical and Computational Sciences Division, NIST. Template Numerical Toolkit (TNT) web page. http://math.nist.gov/tnt/.
• 68: Mathematical and Computational Sciences Division, NIST and The MathWorks. JAMA library web page. http://math.nist.gov/jama/.
• 69: Mathematics and Computer Science Division at Argonne National Laboratory. Portable Extensible Toolkit for Scientific Computation (PETSc) web page. http://www.mcs.anl.gov/petsc.
• 70: J. A. McDonald, Object-oriented programming for linear algebra, Conference proceedings on Object-oriented programming systems, languages and applications, p.175-184, October 02-06, 1989, New Orleans, Louisiana, United States
• 71: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 72: José E. Moreira , Samuel P. Midkiff , Manish Gupta, From Flop to MegaFlops: Java for Technical Computing, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.1-17, August 07-09, 1998
• 73: J. E. Moreira, S. P. Midkiff, and M. Gupta. A standard Java array package for technical computing. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, March 1999.
• 74: Eric Noulard , Nahid Emad, Object Oriented Design for Reusable Parallel Linear Algebra Software, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.1385-1392, August 31-September 03, 1999
• 75: Numerical Objects A.S. Diffpack web page. http://www.nobjects.com.
• 76: R. Parsons and D. Quinlan. A++/P++ array classes for architecture independent finite difference computations. In Proceedings of the Second Annual Object-Oriented Numerics Conference (OON-SKI'94), pages 408-418, 1994.
• 77: R. Pozo. Template numerical toolkit for linear algebra: High performance programming with C++ and the Standard Template Library. The International Journal of Supercomputer Applications and High Performance Computing, 11(3):251-263, 1997.
• 78: R. Pozo, K. A. Remington, and A. Lumsdaine. SparseLib++ v. 1.5: Sparse Matrix Class Library Reference Guide, April 1996. Available at http://math.nist.gov/sparselib++/.
• 79: Jeremy G. Siek , Andrew Lumsdaine, The Matrix Template Library: A Generic Programming Approach to High Performance Numerical Linear Algebra, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.59-70, December 08-11, 1998
• 80: Jeremy G. Siek , Andrew Lumsdaine, The Matrix Template Library: A Unifying Framework for Numerical Linear Algebra, Workshop ion on Object-Oriented Technology, p.466-467, July 20-24, 1998
• 81: Jeremy G. Siek , Andrew Lumsdaine, A Rational Approach to Portable High Performance: The Basic Linear Algebra Instruction Set (BLAIS) and the Fixed Algorithm Size Template (FAST) Library, Workshop ion on Object-Oriented Technology, p.468-469, July 20-24, 1998
• 82: Jeremy G. Siek , Andrew Lumsdaine, The Matrix Template Library: Generic Components for High-Performance Scientific Computing, Computing in Science and Engineering, v.1 n.6, p.70-78, November 1999 [doi>10.1109/5992.805137]
• 83: J. G. Siek, A. Lumsdaine, and L.-Q. Lee. Generic programming for high performance numerical linear algebra. In M. E. Henderson, C. R. Anderson, and S. L. Lyons, editors, Object Oriented Methods for Interoperable Scientific and Engineering Computing, SIAM Proceedings in Applied Mathematics, 1999.
• 84: Sparse Matrix Object-oriented Ordering methods (SMOOTH) web page. http://www.cs.yorku.ca/ joseph/Smooth/SMOOTH.html.
• 85: SparseLib++ library web page. http://math.nist.gov/sparselib++/.
• 86: Sparse Object Oriented Linear Equations Solver (SPOOLES) web page. http://www.netlib.org/linalg/spooles/spooles.2.2.html.
• 87: G. W. Stewart. Introduction to Matrix Computations. Academic Press, 1973.
• 88: G. W. Stewart. The Jampack Owner's Manual, 1999. Available at ftp://thales.cs.umd/pub/Jampack/AboutJampack.html.
• 89: L. N. Trefethen and D. Bau III. Numerical Linear Algebra. SIAM Press, 1997.
• 90: T. L. Veldhuizen. Expression templates. C++ Report, 7(5):26-31, June 1995.
• 91: Todd L. Veldhuizen, Arrays in Blitz++, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.223-230, December 08-11, 1998

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

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: Java

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance, Theory

Keywords:
Java, numerical linear algebra, object orientation