skip to main content
10.1145/1005285.1005304acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

FFPACK: finite field linear algebra package

Published: 04 July 2004 Publication History

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]
A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
[2]
D. Bini and V. Pan. Polynomial and Matrix Computations, Vol. 1: Fundamental Algorithms. Birkhauser, 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]
J.-G. Dumas, T. Gautier, and C. Pernet. Finite field linear algebra subroutines. ISSAC'2002, Lille, France, pp 63--74.
[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]
J.-G. Dumas and J.-L. Roch. On parallel block algorithms for exact triangularizations. Parallel Computing, 28(11):1531--1548, Nov. 2002.
[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]
P. Giorgi, C.-P. Jeannerod, and G. Villard. On the complexity of polynomial matrix computations. ISSAC'2003, Philadelphia, USA, pp 135--142.
[14]
F. Gustavson, A. Henriksson, I. Jonsson, and B. Kaagstroem. Recursive blocked data formats and BLAS's for dense linear algebra algorithms. Lecture Notes in Computer Science, 1541:195--206, 1998.
[15]
X. Huang and V. Y. Pan. Fast rectangular matrix multiplications and improving parallel matrix computations. PASCO'97, Maui, USA, pp 11--23.
[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]
W. J. Turner. Blackbox linear algebra with the LinBox library. PhD thesis, NC State University, May 2002.
[22]
R. C. Whaley, A. Petitet, and J. J. Dongarra. Automated empirical optimizations of software and the ATLAS project.

Cited By

View all
  • (2025)On the arithmetic complexity of computing Gröbner bases of comaximal determinantal idealsJournal of Algebra10.1016/j.jalgebra.2025.01.014668(233-264)Online publication date: Apr-2025
  • (2018)Fast matrix multiplication and its algebraic neighbourhoodSbornik: Mathematics10.1070/SM8833208:11(1661-1704)Online publication date: 29-Jan-2018
  • (2017)Быстрое умножение матриц и смежные вопросы алгебрыFast matrix multiplication and its algebraic neighborhoodМатематический сборникMatematicheskii Sbornik10.4213/sm8833208:11(90-138)Online publication date: 2017
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation
July 2004
334 pages
ISBN:158113827X
DOI:10.1145/1005285
  • General Chair:
  • Josef Schicho
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 July 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. BLAS
  2. LSP factorization
  3. finite fields

Qualifiers

  • Article

Conference

ISSAC04
Sponsor:

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)1
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)On the arithmetic complexity of computing Gröbner bases of comaximal determinantal idealsJournal of Algebra10.1016/j.jalgebra.2025.01.014668(233-264)Online publication date: Apr-2025
  • (2018)Fast matrix multiplication and its algebraic neighbourhoodSbornik: Mathematics10.1070/SM8833208:11(1661-1704)Online publication date: 29-Jan-2018
  • (2017)Быстрое умножение матриц и смежные вопросы алгебрыFast matrix multiplication and its algebraic neighborhoodМатематический сборникMatematicheskii Sbornik10.4213/sm8833208:11(90-138)Online publication date: 2017
  • (2017)On the arithmetic complexity of Strassen-like matrix multiplicationsJournal of Symbolic Computation10.1016/j.jsc.2016.07.00480:P2(484-501)Online publication date: 1-May-2017
  • (2016)Modular SIMD arithmetic in MathemagixACM Transactions on Mathematical Software10.1145/287650343:1(1-37)Online publication date: 29-Aug-2016
  • (2016)Auto-tuning TRSM with an asynchronous task assignment model on multicore, multi-GPU and coprocessor systems2016 IEEE/ACS 13th International Conference of Computer Systems and Applications (AICCSA)10.1109/AICCSA.2016.7945637(1-8)Online publication date: Nov-2016
  • (2015)Neighbor Discovery in Wireless Networks with Multipacket ReceptionIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.232115726:7(1984-1998)Online publication date: 1-Jul-2015
  • (2014)Algebraic Algorithms*Computing Handbook, Third Edition10.1201/b16812-13(1-30)Online publication date: 8-May-2014
  • (2014)A Practical Implementation of a Modular Algorithm for Ore Polynomial MatricesComputer Mathematics10.1007/978-3-662-43799-5_5(49-59)Online publication date: 1-Oct-2014
  • (2012)The M4RIE library for dense linear algebra over small fields with even characteristicProceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442838(28-34)Online publication date: 22-Jul-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media