Computer Science – Symbolic Computation
Scientific paper
2006-01-31
ACM Transactions on Mathematical Software 35, 3 (2009) article 19
Computer Science
Symbolic Computation
Scientific paper
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 p-adic lifting allow very good practical performance, especially when word size arithmetic are used. Therefore, finite field arithmetic becomes an important core for efficient exact linear algebra libraries. In this paper, we study high performance implementations of basic linear algebra routines over word size prime fields: specially the matrix multiplication; our goal being to provide an exact alternate to the numerical BLAS library. We show that this is made possible by a carefull 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.
Dumas Jean-Guillaume
Giorgi Pascal
Pernet Clément
No associations
LandOfFree
Dense Linear Algebra over Finite Fields: the FFLAS and FFPACK packages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dense Linear Algebra over Finite Fields: the FFLAS and FFPACK packages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dense Linear Algebra over Finite Fields: the FFLAS and FFPACK packages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-353635