Generic matrix multiplication and memory management in linBox

ABSTRACT

We describe the design and implementation of two components in the LinBox library. The first is an implementation of black box matrix multiplication as a lazy matrix-times-matrix product. The implementation uses template meta-programming to set the intermediate vector type used during application of the matrix product. We also describe an interface mechanism that allows incorporation of external components with native memory management such as garbage collection into LinBox. An implementation of the interface based on SACLIB's field arithmetic procedures is presented.

REFERENCES

• 1: Boost C++ libraries, 2003. URL:http://www.boost.org.
• 2: Brown, C. Saclib2.1 on Linux. http://www.cis.udel.edu/~saclib/linux/SaclibLinux.html, Mar. 2000.
• 3: Chen, L., Eberly, W., Kaltofen, E., Saunders, B. D., Turner, W. J., and Villard, G. Efficient matrix preconditioners for black box linear algebra. Linear Algebra and Applications 343--344 (2002), 119--146.
• 4: Cohen, A. M., Gao, X.-S., and Takayama, N., Eds. Proc. First Internat. Congress Math. Software ICMS 2002, Beijing, China (Singapore, 2002), World Scientific.
• 5: Dumas, J.-G., Gautier, T., Giesbrecht, M., Giorgi, P., Hovinen, B., Kaltofen, E., Saunders, B. D., Turner, W. J., and Villard, G. LinBox: A generic library for exact linear algebra. In Cohen et al. {4}, pp. 40--50.
• 6: Jean-Guillaume Dumas , Pascal Giorgi , Clément Pernet, FFPACK: finite field linear algebra package, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.119-126, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005304]
• 7: GNU compiler collection, 2003. FSF - Free Software Foundation Gnu Project: URL: http://gcc.gnu.org.
• 8: Gutierrez, J., Ed. ISSAC 2004 Proc. 2004 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2004), ACM Press.
• 9: ISO/IEC. International standard, programming languages---C++. No. 14882:1998(E). American National Standards Institute, New York, 1998.
• 10: Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
• 11: Musser, D. R., Derge, G. J., and Saini, A. STL Reference Guide, second ed. Addison-Wesley, Reading, MA, 2001.
• 12: P.J. Plauger , Meng Lee , David Musser , Alexander A. Stepanov , Alexander Stepanov, C++ Standard Template Library, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 13: David Saunders , Zhendong Wan, Smith normal form of dense integer matrices fast algorithms into practice, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.274-281, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005325]
• 14: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 15: Vielhaber, H., Buchberger, B., Collins, G. E., Encarnación, M. J., Hong, H., Johnson, J. R., Krandick, W., Loos, R., and Mandache, A. N. A. M. SACLIB 1.1 user's guide. Tech. Rep. 93-19, RISC Linz, Linz, Austria, 1993.
• 16: Watt, S. M. A study in the integration of computer algebra systems: Memory management in the Maple-Aldor environment. In Cohen et al. {4}, pp. 405--410.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

General Terms:
Design, Languages

Keywords:
C++ allocator, C++ templates, black box matrix, exact linear algebra, garbage collection, memory management, system integration