Title | Certified dense linear system solving |
Author(s) | Thom Mulders, Arne Storjohann |
Type | Article in Journal |
Abstract | A randomized algorithm is given for solving a system of linear equations over a principal ideal domain. The algorithm returns a solution vector which has minimal denominator. A certificate of minimality is also computed. A given system has a Diophantine solution precisely when the minimal denominator is one. Cost estimates are given for systems over the ring of integers and ring of polynomials with coefficients from a field. |
Keywords | Linear system solution, Diophantine system solution, Integer matrix, Polynomial matrix, Randomized algorithm, Las Vegas |
ISSN | 0747-7171 |
URL |
http://www.sciencedirect.com/science/article/pii/S0747717103001214 |
Language | English |
Journal | Journal of Symbolic Computation |
Volume | 37 |
Number | 4 |
Pages | 485 - 510 |
Year | 2004 |
Edition | 0 |
Translation |
No |
Refereed |
No |