[racket-dev] [plt] Push #25941: master branch updated

On 12/22/2012 11:02 AM, Jens Axel Søgaard wrote:
> 2012/12/22  <ntoronto at racket-lang.org>:
>> 1aebd17 Neil Toronto <ntoronto at 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.

Didn't think of that. Ew.

> According to
>      https://www.cs.drexel.edu/~wan/publications/thesis.pdf
> page 33 Gauss elimation turns onto a O(n^4) algorithm.

Double ew. O(n^3) is bad enough.

I'll put it back in like you had it: partial pivot option exists, 
default on. What would you think of using the type (U 'nonzero 'partial) 
for it, so we could extend it to (U 'nonzero 'partial 'full) sometime in 
the future?

Somewhat related, it looks like if I write this matrix constructor:

   (: permutation-matrix : (Sequenceof Integer) -> (Matrix (U 0 1)))

it would be pretty easy to write a PLU decomposition function. (The 
input sequence would be a mapping from input row numbers to output row 
numbers for a column matrix multiplied on the result's right side.) Does 
that sound right to you?

(Also, because `permutation-matrix' would be such a cheap function to 
call - it wouldn't even allocate memory for the elements - we'd probably 
want `matrix-lu' to return a PLU decomposition anyway.)

Neil ⊥