Academic
Publications
Finite field linear algebra subroutines

Finite field linear algebra subroutines,10.1145/780506.780515,Jean-Guillaume Dumas,Thierry Gautier,Clément Pernet

Finite field linear algebra subroutines   (Citations: 39)
BibTex | RIS | RefWorks Download
In this paper we study different implementations of finite field arithmetic, essential foundation of computer algebra. We focus on Galois fields of word size cardinality at most, with any characteristic. Classical representations as machine integers, floating point numbers, polynomials and Zech logarithms are compared. Furthermore, very efficient implementations of finite field dot products, matrix-vector products and matrix-matrix products (namely the symbolic equivalent of level 1, 2 and 3 BLAS) are presented. Our implementations have many symbolic linear algebra applications: symbolic triangularization, system solving, exact determinant computation, matrix normal form are such examples.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The single problem of computing a nullspace over Q(x) thus provides a good test of, and should motivate the further development of, highly optimized libraries such as GMP [3], FFLAS [1], FLINT [4] and zn poly [5]...

    Burçin Eröcalet al. Nullspace computation over rational function fields for symbolic summa...

    • ...The first idea consists in using the numerical methods in an exact way as done for dense matrix operations [7]...
    • ...In order to adapt current LinBox’s implementation to extension field, we will use the same technique as [7]: first use Kronecker substitution to transform the extension field polynomial representation to an integer representation ; then use a Chinese remaindered version of the polynomial matrix multiplication to recover the resulting matrix polynomial over Z ; and finally convert back the integers using e.g...

    Brice BoyerJean-Guillaumeet al. Exact Sparse Matrix-Vector Multiplication on GPU's and Multicore Archi...

    • ...On optimization of linear algebra library, contemporary research focuses on an algorithmic level [2,3]...

    Yun Xuet al. Optimization of Triangular Matrix Functions in BLAS Library on Loongso...

    • ...Former studies on how to turn this algorithm into practice can be found in [2, 9, 10, 6] and references therein for numerical computation and in [15, 7] for computations over a nite eld...

    Brice Boyeret al. Memory efficient scheduling of Strassen-Winograd's matrix multiplicati...

    • ...Some of the ideas from preliminary versions of this paper [17], in particular the BLAS-based matrix multiplication for small prime fields, are now incorporated into the Maple computer algebra system since its version 8 and also into the 2005 version of the computer algebra system Magma...
    • ...Extending the work undertaken by the authors et al.[41, 17, 4, 25, 14, 18, 20], this paper focuses on matrix multiplication with an extended Winograd variant optimizing memory allocation ; on simultaneous triangular system solving; on matrix factorization and improved constant factors of complexity for many linear algebra equivalent routines (inverse, squaring, upper-lower or upper-upper triangular multiplication, etc.)...
    • ...The main result of this section is that, in the worst case, the largest intermediate computation occurs during the recursive computation of the sixth recursive product P6 (see appendix A). This result generalizes [17, theorem 3.1] for the computation of AB + βC. Theorem 3.1...
    • ...By reusing BLAS library this has been proven to be almost useless for matrix multiplication in [17] and we think we proved here that this is not mandatory also for any dense linear algebra routine...

    Jean-guillaume Dumaset al. Dense Linear Algebra over Word-Size Prime Fields: the FFLAS and FFPACK...

Sort by: