Generic compressed sparse matrix insertion: algorithms and implementations in MTL4 and FEniCS

ABSTRACT

Sparse matrices are indispensable components of most scientific applications. Nevertheless, there is very little general-purpose software support. With the Matrix Template Library 4 (MTL4) we provide a generic library support for dense and compressed sparse matrices. The first challenge in working with compressed matrices is how to set the nonzero entries in an efficient manner. The implementation in MTL4 does not need any pre-allocation or pre-sorting phase, uses a minimal amount of memory and was in all measures as fast or faster than comparable libraries. We demonstrate the performance on well-defined benchmarks.

REFERENCES

• 1: M. O. Deville, P. F. Fischer, and E. H. Mund. High-Order Methods for Incompressible Fluid Flow. Cambridge University Press, 2002.
• 2: Göddeke et al. Using GPUs to improve multigrid solver performance on a cluster. IJCSE.
• 3: R. Barrett et al. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM Press, Philadelphia, 1994.
• 4: S. Balay et al. (PETSc team). PETSc Web page, 2001. http://www.mcs.anl.gov/petsc.
• 5: F. Alet et al. (the ALPS coll.). The ALPS project: open source software for strongly correlated systems. J. PHYS. SOC. JPN., 74:30, 2005.
• 6: G. C Fox. Matrix operations on the homogeneous machine. Technical report, California Institute of Technology, Pasadena, CA, July 1982.
• 7: Jens Gerlach , Peter Gottschling , Uwe Der, A Generic C++ Framework for Parallel Mesh-Based Scientific Applications, Proceedings of the 6th International Workshop on High-Level Parallel Programming Models and Supportive Environments, p.45-54, April 23, 2001
• 8: Peter Gottschling , David S. Wise , Michael D. Adams, Representation-transparent matrix algorithms with scalable performance, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1274989]
• 9: P. Gottschling, D. S. Wise, and A. Joshi. Generic support of algorithmic and structural recursion for scientific computing. In POOSC'09 at ECOOP08, Cyprus, Greece, 2008.
• 10: J. Hoffman, J. Jansson, A. Logg, G. N. Wells, et al. DOLFIN. http//www.fenics.org/dolfin/, 2006.
• 11: Robert C. Kirby , Anders Logg, A compiler for variational forms, ACM Transactions on Mathematical Software (TOMS), v.32 n.3, p.417-444, September 2006 [doi>10.1145/1163641.1163644]
• 12: Andrew Lumsdaine, Jeremy Siek, Lie-Quan Lee, and Peter Gottschling. The Matrix Template Library home page. http://www.osl.iu.edu/research/mtl, 2006.
• 13: J. Siek, L.-Q. Lee, and A. Lumsdaine. The Boost Graph Library. Addison-Wesley, Boston, MA, USA, 2002.
• 14: 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
• 15: Simon Vey , Axel Voigt, AMDiS: adaptive multidimensional simulations, Computing and Visualization in Science, v.10 n.1, p.57-67, February 2007 [doi>10.1007/s00791-006-0048-3]
• 16: Jörg Walter and Mathias Koch. uBLAS -- Boost Basic Linear Algebra. www.boost.org/doc/libs/release/libs/numeric/ublas/doc/index.htm, 2002.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries
      D.2.3 Coding Tools and Techniques
          Subjects: Object-oriented programming

Keywords:
FEniCS, generic programming, matrix template library, sparse matrices