Fast matrix decomposition in \(\mathbb F_2\). (English) Zbl 1293.65067

Summary: In this work an efficient algorithm to perform a block decomposition for large dense rectangular matrices with entries in \(\mathbb F_2\) is presented. Matrices are stored as column blocks of row major matrices in order to facilitate rows operation and matrix multiplications with blocks of columns. One of the major bottlenecks of matrix decomposition is the pivoting involving both rows and column exchanges. Since row swaps are cheap and column swaps are order of magnitude slower, the number of column swaps should be reduced as much as possible. Here an algorithm that completely avoids the column permutations is presented. An asymptotically fast algorithm is obtained by combining the four Russian algorithm and the recursion with the Strassen algorithm for matrix-matrix multiplication. Moreover optimal parameters for the tuning of the algorithm are theoretically estimated and then experimentally verified. A comparison with the state of the art public domain software SAGE shows that the proposed algorithm is generally faster.


65F30 Other matrix algorithms (MSC2010)
15A23 Factorization of matrices
68Q25 Analysis of algorithms and problem complexity
94A60 Cryptography
Full Text: DOI arXiv


[1] Meyer, C. D., Matrix analysis and applied linear algebra, (2000), Society for Industrial and Applied Mathematics Philadelphia, PA, USA
[2] Golub, G. H.; Van Loan, C. F., (Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences, (1996), Johns Hopkins University Press Baltimore, MD)
[3] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356, (1969) · Zbl 0185.40101
[4] Winograd, S., On multiplication of \(2 \times 2\) matrices, Linear Algebra Appl., 4, 381-388, (1971) · Zbl 0225.68018
[5] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9, 251-280, (1990) · Zbl 0702.65046
[6] Huss-Lederman, S.; Jacobson, E. M.; Tsao, A.; Turnbull, T.; Johnson, J. R., Implementation of strassen’s algorithm for matrix multiplication, (Proceedings of the 1996 ACM/IEEE Conference on Supercomputing (CDROM), Supercomputing’96, (1996), IEEE Computer Society Washington, DC, USA)
[7] Higham, N. J., Exploiting fast matrix multiplication within the level 3 BLAS, ACM Trans. Math. Software, 16, 352-368, (1990) · Zbl 0900.65118
[8] Douglas, C. C.; Heroux, M.; Slishman, G.; Smith, R. M., GEMMW: a portable level 3 blas Winograd variant of strassen’s matrix-matrix multiply algorithm, J. Comput. Phys., 110, 1-10, (1994) · Zbl 0793.65031
[9] Kaporin, I., A practical algorithm for faster matrix multiplication, Numer. Linear Algebra Appl., 6, 687-700, (1999) · Zbl 0982.65048
[10] Arlazarov, V. L.; Dinic, E. A.; Kronrod, M. A.; Faradžev, I. A., On economical construction of the transitive closure of a directed graph, Sov. Math. Dokl., 11, 1209-1210, (1970) · Zbl 0214.23601
[11] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The design and analysis of computer algorithms, (1974), Addison-Wesley Publishing Company Boston, Massachusetts · Zbl 0207.01701
[12] Albrecht, M.; Bard, G.; Hart, W., Algorithm 898: efficient multiplication of dense matrices over \(\operatorname{GF}(2)\), ACM Trans. Math. Software, 37, 9:1-9:14, (2010) · Zbl 1364.65092
[13] Shoup, V., A computational introduction to number theory and algebra, (2009), Cambridge University Press · Zbl 1196.11002
[14] Bach, E.; Shallit, J., (Algorithmic Number Theory: Efficient Algorithms, Foundations of computing, (1996), MIT Press Cambridge, USA)
[15] Gerver, J. L., Factoring large numbers with a quadratic sieve, Math. Comp., 41, 287-294, (1983) · Zbl 0527.10003
[16] LaMacchia, B.; Odlyzko, A., Computation of discrete logarithms in prime fields, Des. Codes Cryptogr., 1, 47-62, (1991) · Zbl 0747.94012
[17] Brent, R., Recent progress and prospects for integer factorisation algorithms, (Du, D.-Z.; Eades, P.; Estivill-Castro, V.; Lin, X.; Sharma, A., Computing and Combinatorics, Lecture Notes in Computer Science, vol. 1858, (2000), Springer Berlin, Heidelberg), 3-22 · Zbl 0988.11056
[18] Lenstra, A. K., Integer factoring, Des. Codes Cryptogr., 19, 101-128, (2000), Towards a quarter-century of public key cryptography · Zbl 0964.11057
[19] LaMacchia, B. A.; Odlyzko, A. M., Solving large sparse linear systems over finite fields, (Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO’90, (1991), Springer-Verlag London, UK), 109-133 · Zbl 0786.65028
[20] Bender, E. A.; Canfield, E. R., An approximate probabilistic model for structured Gaussian elimination, J. Algorithms, 31, 271-290, (1999) · Zbl 0921.68043
[21] Coppersmith, D., Solving linear equations over GF(2): block Lanczos algorithm, Linear Algebra Appl., 192, 33-60, (1993), Computational linear algebra in algebraic and related problems (Essen, 1992) · Zbl 0788.65038
[22] Peterson, M.; Monico, C., \(\mathbb{F}_2\) Lanczos revisited, Linear Algebra Appl., 428, 1135-1150, (2008) · Zbl 1165.65024
[23] Wiedemann, D. H., Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory, 32, 54-62, (1986) · Zbl 0607.65015
[24] Coppersmith, D., Solving homogeneous linear equations over \(\operatorname{GF}(2)\) via block wiedemann algorithm, Math. Comp., 62, 333-350, (1994) · Zbl 0805.65046
[25] T. Gautier, J.-L. Roch, G. Villard, Givaro: C++ library for arithmetic and algebraic computations, 2013. http://http://givaro.forge.imag.fr.
[26] Dumas, J.-G.; Giorgi, P.; Pernet, C., Dense linear algebra over word-size prime fields: the FFLAS and FFPACK packages, ACM Trans. Math. Software, 35, 35, (2008), Art. 19
[27] Anderson, E.; Bai, Z.; Bischof, C.; Blackford, L. S.; Demmel, J.; Dongarra, J. J.; Du Croz, J.; Hammarling, S.; Greenbaum, A.; McKenney, A.; Sorensen, D., LAPACK users’ guide, (1999), Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 0934.65030
[28] Dumas, J.-G., Linbox: a generic library for exact linear algebra, (Cohen, A.; Gao, X.-S.; Takayama, N., Mathematical Software: ICMS 2002 (Proceedings of the first International Congress of Mathematical Software), (2002), World Scientific), 40-50 · Zbl 1011.68182
[29] M. Albrecht, G. Bard, The M4RI library, The M4RI Team, 2012. URL http://m4ri.sagemath.org.
[30] W. Stein, et al. Sage mathematics software (Version 5.2), The Sage Development Team, 2012. http://www.sagemath.org.
[31] Bosma, W.; Cannon, J.; Playoust, C., The magma algebra system, I. the user language, J. Symbolic Comput., 24, 235-265, (1997), Computational algebra and number theory (London, 1993) · Zbl 0898.68039
[32] Haynsworth, E., On the Schur complement, (1968), Defense Technical Information Center, Basel University
[33] Zhang, F., (The Schur Complement and its Applications, Numerical Methods and Algorithms, (2005), Springer Science) · Zbl 1075.15002
[34] Albrecht, M. R.; Bard, G. V.; Pernet, C., Efficient dense Gaussian elimination over the finite field with two elements, technical report, cornell university library, (2011), URL http://arxiv.org/abs/1111.6549
[35] Jeannerod, C.-P.; Pernet, C.; Storjohann, A., Rank-profile revealing Gaussian elimination and the {CUP} matrix decomposition, J. Symbolic. Comput., 56, 46-68, (2013) · Zbl 1329.65065
[36] Ben-Israel, A.; Greville, T. N., (Generalized Inverses. Theory and Applications, CMS Books in Mathematics, (2003), Springer) · Zbl 1026.15004
[37] Kincaid, D.; Cheney, E., (Numerical Analysis: mathematics of Scientific Computing, Pure and Applied Undergraduate Texts, (2002), American Mathematical Society)
[38] (Olver, F. J.; Lozier, D.; Boisvert, R.; Clark, C., NIST Handbook of Mathematical Functions, (2010), US Department of Commerce National Institute of Standards and Technology Washington, DC), With CD-ROM · Zbl 1198.00002
[39] Andrén, D.; Hellstrom, L.; Markstrom, K., On the complexity of matrix reduction over finite fields, Adv. in Appl. Math., 39, 428-452, (2007) · Zbl 1132.65018
[40] E. Bertolazzi, GF2toolkit, 2013. URL https://github.com/ebertolazzi/GF2toolkit.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.