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 |