{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T07:39:32Z","timestamp":1778657972136,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,10,1]],"date-time":"2008-10-01T00:00:00Z","timestamp":1222819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2008,10]]},"abstract":"<jats:p>\n            In the past two decades, some major efforts have been made to reduce exact (e.g. integer, rational, polynomial) linear algebra problems to matrix multiplication in order to provide algorithms with optimal asymptotic complexity. To provide efficient implementations of such algorithms one need to be careful with the underlying arithmetic. It is well known that modular techniques such as the Chinese remainder algorithm or the\n            <jats:italic>p<\/jats:italic>\n            -adic lifting allow very good practical performance, especially when word size arithmetic is used. Therefore, finite field arithmetic becomes an important core for efficient exact linear algebra libraries. In this article, we study high performance implementations of basic linear algebra routines over word size prime fields: especially matrix multiplication; our goal being to provide an exact alternate to the numerical BLAS library. We show that this is made possible by a careful combination of numerical computations and asymptotically faster algorithms. Our kernel has several symbolic linear algebra applications enabled by diverse matrix multiplication reductions: symbolic triangularization, system solving, determinant, and matrix inverse implementations are thus studied.\n          <\/jats:p>","DOI":"10.1145\/1391989.1391992","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T13:49:43Z","timestamp":1225979383000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":59,"title":["Dense Linear Algebra over Word-Size Prime Fields"],"prefix":"10.1145","volume":"35","author":[{"given":"Jean-Guillaume","family":"Dumas","sequence":"first","affiliation":[{"name":"Universit\u00e9 Joseph Fourier"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Giorgi","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Montpellier 2 and Universit\u00e9 de Perpignan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cl\u00e9ment","family":"Pernet","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,10]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley. Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms . Addison-Wesley."},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Anderson E. Bai Z. Bischof C. Blackford S. Demmel J. Dongarra J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. 1999. LAPACK Users\u2019 Guide Third ed. Society for Industrial and Applied Mathematics Philadelphia PA. Anderson E. Bai Z. Bischof C. Blackford S. Demmel J. Dongarra J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. 1999. LAPACK Users\u2019 Guide Third ed. Society for Industrial and Applied Mathematics Philadelphia PA.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Bini D. and Pan V. 1994. Polynomial and Matrix Computations Volume 1: Fundamental Algorithms. Birkhauser Boston. Bini D. and Pan V. 1994. Polynomial and Matrix Computations Volume 1: Fundamental Algorithms. Birkhauser Boston.","DOI":"10.1007\/978-1-4612-0265-3_1"},{"key":"e_1_2_2_4_1","unstructured":"Brassel M. Giorgi P. and Pernet C. 2003. LUdivine: A symbolic block LU factorisation for matrices over finite fields using BLAS. Poster http:\/\/ljk.imag.fr\/membres\/Jean&minus;Guillaume.Dumas\/FFLAS\/FFLAS_Download\/ludivine_poster_eccad2003.ps.gz. Brassel M. Giorgi P. and Pernet C. 2003. LUdivine: A symbolic block LU factorisation for matrices over finite fields using BLAS. Poster http:\/\/ljk.imag.fr\/membres\/Jean&minus;Guillaume.Dumas\/FFLAS\/FFLAS_Download\/ludivine_poster_eccad2003.ps.gz."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0331751-8"},{"key":"e_1_2_2_6_1","volume-title":"9th International Conference on Applications of Computer Algebra (ACA\u20192003)","author":"Chen Z.","unstructured":"Chen , Z. and Storjohann , A . 2003. Effective reductions to matrix multiplication . 9th International Conference on Applications of Computer Algebra (ACA\u20192003) , Raleigh, North Carolina State University. Chen, Z. and Storjohann, A. 2003. Effective reductions to matrix multiplication. 9th International Conference on Applications of Computer Algebra (ACA\u20192003), Raleigh, North Carolina State University."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_2_8_1","first-page":"2","article-title":"Fast computation of Moore-Penrose inverse matrices","volume":"8","author":"Courrieu P.","year":"2005","unstructured":"Courrieu , P. 2005 . Fast computation of Moore-Penrose inverse matrices . Neural Information Processing - Letters and Reviews 8 , 2 (Aug.), 25--29. Courrieu, P. 2005. Fast computation of Moore-Penrose inverse matrices. Neural Information Processing - Letters and Reviews 8, 2 (Aug.), 25--29.","journal-title":"Neural Information Processing - Letters and Reviews"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459082"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1757599.1757688"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1994.1001"},{"key":"e_1_2_2_13_1","unstructured":"Dumas J.-G. Giorgi P. and Pernet C. 2006. FFLAS-FFPACK: Finite field linear algebra subroutine\/package. Software http:\/\/ciel.ccsd.cnrs.fr\/ciel&minus;00000025. Feb. Dumas J.-G. Giorgi P. and Pernet C. 2006. FFLAS-FFPACK: Finite field linear algebra subroutine\/package. Software http:\/\/ciel.ccsd.cnrs.fr\/ciel&minus;00000025. Feb."},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the Seventh International Workshop on Computer Algebra in Scientific Computing","author":"Dumas J.-G.","year":"2004","unstructured":"Dumas , J.-G. 2004 . Efficient dot product over finite fields . In Proceedings of the Seventh International Workshop on Computer Algebra in Scientific Computing , ( Yalta, Ukraine). V. G. Ganzha, E. W. Mayr, and E. V. Vorozhtsov, Eds. Technische Universit\u00e4t M\u00fcnchen, Germany, 139--154. Dumas, J.-G. 2004. Efficient dot product over finite fields. In Proceedings of the Seventh International Workshop on Computer Algebra in Scientific Computing, (Yalta, Ukraine). V. G. Ganzha, E. W. Mayr, and E. V. Vorozhtsov, Eds. Technische Universit\u00e4t M\u00fcnchen, Germany, 139--154."},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the 2002 International Congress of Mathematical Software","author":"Dumas J.-G.","unstructured":"Dumas , J.-G. , Gautier , T. , Giesbrecht , M. , Giorgi , P. , Hovinen , B. , Kaltofen , E. , Saunders , B. D. , Turner , W. J. , and Villard , G . 2002a. LinBox: A generic library for exact linear algebra . In Proceedings of the 2002 International Congress of Mathematical Software ( Beijing, China). A. M. Cohen, X.-S. Gao, and N. Takayama, Eds. World Scientific Pub, 40--50. Dumas, J.-G., Gautier, T., Giesbrecht, M., Giorgi, P., Hovinen, B., Kaltofen, E., Saunders, B. D., Turner, W. J., and Villard, G. 2002a. LinBox: A generic library for exact linear algebra. In Proceedings of the 2002 International Congress of Mathematical Software (Beijing, China). A. M. Cohen, X.-S. Gao, and N. Takayama, Eds. World Scientific Pub, 40--50."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/780506.780515"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005285.1005304"},{"key":"e_1_2_2_19_1","volume-title":"-L","author":"Dumas J.-G.","year":"2006","unstructured":"Dumas , J.-G. , Pernet , C. , and Roch , J . -L . 2006 . Adaptive triangular system solving. In Challenges in Symbolic Computation Software. Dagstuhl Seminar proceedings 06271, paper 770. Dumas, J.-G., Pernet, C., and Roch, J.-L. 2006. Adaptive triangular system solving. In Challenges in Symbolic Computation Software. Dagstuhl Seminar proceedings 06271, paper 770."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073884.1073905"},{"key":"e_1_2_2_21_1","unstructured":"Dumas J.-G. Pernet C. and Zhou W. 2007. Memory efficient scheduling of Strassen-Winograd\u2019s matrix multiplication algorithm. Tech. rep. arXiv:0707.2347v2. Aug. http:\/\/arxiv.org\/abs\/0707.2347v2. Dumas J.-G. Pernet C. and Zhou W. 2007. Memory efficient scheduling of Strassen-Winograd\u2019s matrix multiplication algorithm. Tech. rep. arXiv:0707.2347v2. Aug. http:\/\/arxiv.org\/abs\/0707.2347v2."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(02)00161-8"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2001.0451"},{"key":"e_1_2_2_24_1","volume-title":"J.","author":"Gathen J.","year":"1999","unstructured":"Gathen , J. v. and Gerhard , J. 1999 . Modern Computer Algebra. Cambridge University Press , New York, NY. Gathen, J. v. and Gerhard, J. 1999. Modern Computer Algebra. Cambridge University Press, New York, NY."},{"key":"e_1_2_2_25_1","volume-title":"9th International Conference on Applications of Computer Algebra (ACA\u20192003)","author":"Giorgi P.","year":"2003","unstructured":"Giorgi , P. 2003 . From BLAS routines to finite field exact linear algebra solutions . 9th International Conference on Applications of Computer Algebra (ACA\u20192003) , Raleigh, North Carolina State University. Giorgi, P. 2003. From BLAS routines to finite field exact linear algebra solutions. 9th International Conference on Applications of Computer Algebra (ACA\u20192003), Raleigh, North Carolina State University."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/860854.860889"},{"key":"e_1_2_2_27_1","volume-title":"Matrix Computations","author":"Golub G. H.","unstructured":"Golub , G. H. and Van Loan , C. F. 1996. Matrix Computations , third ed. Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press , Baltimore, MD. Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations, third ed. Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore, MD."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/645781.666659"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/98267.98290"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/369028.369096"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Huss-Lederman S. Jacobson E. M. Johnson J. R. Tsao A. and Turnbull T. 1996b. Strassen\u2019s algorithm for matrix multiplication : modeling analysis and implementation. Tech. rep. Center for Computing Sciences. Nov. CCS-TR-96-17. Huss-Lederman S. Jacobson E. M. Johnson J. R. Tsao A. and Turnbull T. 1996b. Strassen\u2019s algorithm for matrix multiplication : modeling analysis and implementation. Tech. rep. Center for Computing Sciences. Nov. CCS-TR-96-17.","DOI":"10.1145\/369028.369096"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90007-4"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0185-3"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.01.004"},{"key":"e_1_2_2_36_1","volume-title":"-H","author":"Laderman J.","year":"1992","unstructured":"Laderman , J. , Pan , V. , and Sha , X . -H . 1992 . On practical algorithms for accelerated matrix multiplication. Linear Algebra Appl . 162--164, 557--588. Laderman, J., Pan, V., and Sha, X.-H. 1992. On practical algorithms for accelerated matrix multiplication. Linear Algebra Appl. 162--164, 557--588."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1985-0777282-X"},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the 1995 International Conference on the Theory and Application of Cryptographic Techniques (Saint-Malo, France). L. C. Guillou and J.-J","author":"Montgomery P. L.","unstructured":"Montgomery , P. L. 1995. A block Lanczos algorithm for finding dependencies over gf(2) . In Proceedings of the 1995 International Conference on the Theory and Application of Cryptographic Techniques (Saint-Malo, France). L. C. Guillou and J.-J . Quisquater, Eds. Lecture Notes in Computer Science , vol. 921 . 106--120. Montgomery, P. L. 1995. A block Lanczos algorithm for finding dependencies over gf(2). In Proceedings of the 1995 International Conference on the Theory and Application of Cryptographic Techniques (Saint-Malo, France). L. C. Guillou and J.-J. Quisquater, Eds. Lecture Notes in Computer Science, vol. 921. 106--120."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0703049"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008350005447"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/384101.384141"},{"key":"e_1_2_2_43_1","unstructured":"Shoup V. 2002. NTL 5.3: A library for doing number theory. www.shoup.net\/ntl. Shoup V. 2002. NTL 5.3: A library for doing number theory. www.shoup.net\/ntl."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2005.04.002"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_2_2_46_1","first-page":"1","article-title":"Automated empirical optimizations of software and the ATLAS project. Para","volume":"27","author":"Whaley R. C.","year":"2001","unstructured":"Whaley , R. C. , Petitet , A. , and Dongarra , J. J. 2001 . Automated empirical optimizations of software and the ATLAS project. Para . Comput. 27 , 1 -- 2 (Jan.), 3--35. http:\/\/www.netlib.org\/utk\/people\/JackDongarra\/PAPERS\/atlas_pub.pdf. Whaley, R. C., Petitet, A., and Dongarra, J. J. 2001. Automated empirical optimizations of software and the ATLAS project. Para. Comput. 27, 1--2 (Jan.), 3--35. http:\/\/www.netlib.org\/utk\/people\/JackDongarra\/PAPERS\/atlas_pub.pdf.","journal-title":"Comput."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1978-0476692-4"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391989.1391992","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1391989.1391992","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:58:05Z","timestamp":1750255085000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391989.1391992"}},"subtitle":["the FFLAS and FFPACK Packages"],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1145\/1391989.1391992"],"URL":"https:\/\/doi.org\/10.1145\/1391989.1391992","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10]]},"assertion":[{"value":"2006-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}