Fast matrix decomposition in F2

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:260

Article

Bertolazzi, Enrico¹  Rimoldi, Anna² 

[1] Univ Trent, Dept Ind Engn, I-38100 Trento, Italy

[2] Univ Trent, Dept Math, I-38100 Trento, Italy

关键词: Software implementation of finite field arithmetic;    Mathematical tools for cryptography;    Linear algebra;    Rank computation;    Matrix decomposition;   

DOI  :  10.1016/j.cam.2013.10.026

来源: Elsevier

【 摘 要 】

In this work an efficient algorithm to perform a block decomposition for large dense rectangular matrices with entries in 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. (C) 2013 Elsevier B.V. All rights reserved.

【 授权许可】

Free