FFPACK: finite field linear algebra package

ABSTRACT

The FFLAS project has established that exact matrix multiplication over finite fields can be performed at the speed of the highly optimized numerical BLAS routines. Since many algorithms have been reduced to use matrix multiplication in order to be able to prove an optimal theoretical complexity, this paper shows that those optimal complexity algorithms, such as LSP factorization, rank determinant and inverse computation can also be the most efficient.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
• 3: M. Brassel, P. Giorgi, and C. Pernet. LUdivine: A symbolic block LU factorization for matrices over finite fields using blas. ECCAD'2003, South Carolina, USA.
• 4: Z. Chen and A. Storjohann. Effective reductions to matrix multiplication. ACA'2003, NC State University, USA.
• 5: J. Dongarra and V. Eijkhout. Self-adapting numerical software and automatic tuning of heuristics. Lecture Notes in Computer Science, 2660:759--770, Jan. 2003.
• 6: J.-G. Dumas. Efficient dot product over word-size finite fields. Rapport de recherche, IMAG-RR1064, Mar. 2004.
• 7: J.-G. Dumas, T. Gautier, M. Giesbrecht, P. Giorgi, B. Hovinen, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard. LinBox: A generic library for exact linear algebra. ICMS'2002, Beijing, China, pp 40--50.
• 8: Jean Guillaume Dumas , Thierry Gautier , Clément Pernet, Finite field linear algebra subroutines, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.63-74, July 07-10, 2002, Lille, France [doi>10.1145/780506.780515]
• 9: J.-G. Dumas, P. Giorgi, and C. Pernet. FFPACK: Finite Field Linear Algebra Package, preliminary version. Research Report, LIP-RR2004-02, Jan. 2004.
• 10: Jean-Guillaume Dumas , Jean-Louis Roch, On parallel block algorithms for exact triangularizations, Parallel Computing, v.28 n.11, p.1531-1548, November 2002 [doi>10.1016/S0167-8191(02)00161-8]
• 11: J.-G. Dumas and G. Villard. Computing the rank of sparse matrices over finite fields. CASC'2002, Yalta, Ukraine, pp 47--62.
• 12: P. Giorgi. From blas routines to finite field exact linear algebra solutions, July 2003. ACA'2003, NC State University, USA.
• 13: Pascal Giorgi , Claude-Pierre Jeannerod , Gilles Villard, On the complexity of polynomial matrix computations, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.135-142, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860889]
• 14: Fred G. Gustavson , André Henriksson , Isak Jonsson , Bo Kågström , Per Ling, Recursive Blocked Data Formats and BLAS's for Dense Linear Algebra Algorithms, Proceedings of the 4th International Workshop on Applied Parallel Computing, Large Scale Scientific and Industrial Problems, p.195-206, June 14-17, 1998
• 15: Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplications and improving parallel matrix computations, Proceedings of the second international symposium on Parallel symbolic computation, p.11-23, July 20-22, 1997, Maui, Hawaii, United States [doi>10.1145/266670.266679]
• 16: O. H. Ibarra, S. Moran, and R. Hui. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of Algorithms, 3(1):45--56, Mar. 1982.
• 17: E. Kaltofen, M. S. Krishnamoorthy, and B. D. Saunders. Parallel algorithms for matrix normal forms. Linear Algebra and its Applications, 136:189--208, 1990.
• 18: C. Pernet. Implementation of Winograd's matrix multiplication over finite fields using ATLAS level 3 BLAS. Technical report, Laboratoire Informatique et Distribution, July 2001. www-id.imag.fr/Apache/RR/RR011122FFLAS.ps.gz.
• 19: C. Pernet. Calcul du polynôme caractéristique sur des corps finis. Master's thesis, University of Delaware, 2003.
• 20: C. Pernet and Z. Wan. LU based algorithms for the characteristic polynomial over a finite field. ISSAC'2003, Philadelphia, USA, pp 135--142. Poster.
• 21: William Jonathan Turner , Erich Kaltofen, Black box linear algebra with the linbox library, 2002
• 22: R. C. Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimizations of software and the ATLAS project.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

General Terms:
Algorithms, Experimentation, Performance

Keywords:
BLAS, LSP factorization, finite fields