2012/12/22 <ntoro...@racket-lang.org>:
> 1aebd17 Neil Toronto <ntoro...@racket-lang.org> 2012-12-21 22:59
> | * Specialized row reduction for determinants; removed option to not do
> | partial pivoting (it's never necessary otherwise)
Partial pivoting is used to reduce round-off error. If the matrix consists
of integers or fraction, then due to exact arithmetic, there is no need
to do partial pivoting.
And it gets worse. It is subtle though. Consider matrices with (exact)
integer entries and Gauss elimination with partial pivoting, the result will be
a matrix with fractions. For each division a gcd computation is needed
to reduce the fraction. This hidden cost is can be large in some cases.
According to
https://www.cs.drexel.edu/~wan/publications/thesis.pdf
page 33 Gauss elimation turns onto a O(n^4) algorithm.
(Geddes mentions the same issue in relation to Gaussian
elimination over a general ring).
Related:
The Sage documentation on LU factorization, imply that besides
no-pivoting, the first-non-zero-variant is useful too:
http://www.sagemath.org/doc/reference/sage/matrix/matrix2.html
In fact the partial pivoting is not used as the default.
/Jens Axel
_________________________
Racket Developers list:
http://lists.racket-lang.org/dev
