Rechte / LizenzIn Copyright - Non-Commercial Use Permitted
The following problems related to linear systems are studied: finding a diophantine solution; finding a rational solution; proving no diophantine solution exists; proving no rational solution exists. These problems are reduced, via randomization, to that of computing an expected constant number of rational solutions of square nonsingular systems using adic lifting. The bit complexity of the latter problem is improved by incorporating fast arithmetic and fast matrix multiplication. The resulting randomized algorithm for certified dense linear system solving has substantially better asymptotic complexity than previous algorithms for either rational or diophantine linear system solving. Mehr anzeigen
Externe LinksSuchen via SFX
Zeitschrift / SerieTechnical Report / ETH Zurich, Department of Computer Science
VerlagETH, Eidgenössische Technische Hochschule, Department of Computer Science, Institute of Scientific Computing
Organisationseinheit02150 - Dep. Informatik / Dep. of Computer Science
AnmerkungenTechnical Reports D-INFK.