Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(10)
Computer Algebra
Efficient Implementation
Finite Field
Finite Field Arithmetic
Floating Point
galois field
Linear Algebra
Matrix Multiplication
Normal Form
level 1
Related Publications
(7)
A Probabilistic Remark on Algebraic Program Testing
Implementation of Strassen's algorithm for matrix multiplication
Solving sparse linear equations over finite fields
Efficient computation of the characteristic polynomial
Encyclopedia of Mathematics and its Applications 20
Subscribe
Academic
Publications
Finite field linear algebra subroutines
Finite field linear algebra subroutines,10.1145/780506.780515,JeanGuillaume Dumas,Thierry Gautier,Clément Pernet
Edit
Finite field linear algebra subroutines
(
Citations: 39
)
BibTex

RIS

RefWorks
Download
JeanGuillaume Dumas
,
Thierry Gautier
,
Clément Pernet
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, matrixvector products and matrixmatrix 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.
Conference:
International Symposium on Symbolic and Algebraic Computation  ISSAC
, pp. 6374, 2002
DOI:
10.1145/780506.780515
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.
(
portal.acm.org
)
(
portal.acm.org
)
Citation Context
(32)
...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öcal
,
et 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 BoyerJeanGuillaume
,
et al.
Exact Sparse MatrixVector Multiplication on GPU's and Multicore Archi...
...On optimization of linear algebra library, contemporary research focuses on an algorithmic level [
2
,3]...
Yun Xu
,
et 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 Boyer
,
et al.
Memory efficient scheduling of StrassenWinograd's matrix multiplicati...
...Some of the ideas from preliminary versions of this paper [
17
], in particular the BLASbased 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, upperlower or upperupper 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...
Jeanguillaume Dumas
,
et al.
Dense Linear Algebra over WordSize Prime Fields: the FFLAS and FFPACK...
References
(20)
Lattices of Compatibly Embedded Finite Fields
(
Citations: 2
)
Wieb Bosma
,
John J. Cannon
,
Allan K. Steel
Journal:
Journal of Symbolic Computation  JSC
, vol. 24, no. 3/4, pp. 351369, 1997
Recursive Blocked Data Formats and BLAS's for Dense Linear Algebra Algorithms
(
Citations: 45
)
Fred G. Gustavson
,
André Henriksson
,
Isak Jonsson
,
Bo Kågström
,
Per Ling
Conference:
Workshop on Applied Parallel Computing  PARA
, pp. 195206, 1998
A Block Lanczos Algorithm for Finding Dependencies Over GF(2)
(
Citations: 70
)
Peter L. Montgomery
Conference:
Theory and Application of Cryptographic Techniques  EUROCRYPT
, pp. 106120, 1995
Automated Empirical Optimization of Software and the ATLAS Project
(
Citations: 431
)
Unknown
Published in 2000.
Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography
(
Citations: 81
)
Daniel V. Bailey
,
Christof Paar
Journal:
Journal of Cryptology  JOC
, vol. 14, no. 3, pp. 153176, 2001
Sort by:
Citations
(39)
Simultaneous modular reduction and Kronecker substitution for small finite fields
(
Citations: 1
)
JeanGuillaume Dumas
,
Laurent Fousse
,
Bruno Salvy
Journal:
Journal of Symbolic Computation  JSC
, vol. 46, no. 7, pp. 823840, 2011
Nullspace computation over rational function fields for symbolic summation
Burçin Eröcal
,
Arne Storjohann
Journal:
ACM Communications in Computer Algebra
, pp. 109110, 2011
Exact Sparse MatrixVector Multiplication on GPU's and Multicore Architectures
(
Citations: 1
)
Brice BoyerJeanGuillaume
,
JeanGuillaume Dumas
,
Pascal Giorgi
Journal:
Computing Research Repository  CORR
, vol. abs/1004.3, pp. 8088, 2010
Optimization of Triangular Matrix Functions in BLAS Library on Loongson2F
Yun Xu
,
Mingzhi Shao
,
Da Teng
Conference:
Network and Parallel Computing  NPC
, pp. 3545, 2010
Memory efficient scheduling of StrassenWinograd's matrix multiplication algorithm
(
Citations: 1
)
Brice Boyer
,
Jeanguillaume Dumas
,
Clément Pernet
,
Wei Zhou
Conference:
International Symposium on Symbolic and Algebraic Computation  ISSAC
, pp. 5562, 2009