Re: [racket-dev] [plt] Push #25941: master branch updated
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
Re: [racket-dev] [plt] Push #25941: master branch updated
On 12/22/2012 11:02 AM, Jens Axel Søgaard wrote: 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. 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 ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] [plt] Push #25941: master branch updated
On Dec 22, 2012, at 1:02 PM, Jens Axel Søgaard wrote: 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). Off topic question. Are you implementing GE as an instance of the GE over rings? If so, is it possible to formulate Unification and Type Inference for say STLC via your math library? Totally off topic. No is a fine answer. _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] [plt] Push #25941: master branch updated
On 12/22/2012 05:04 PM, Matthias Felleisen wrote: On Dec 22, 2012, at 1:02 PM, Jens Axel Søgaard wrote: 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). Off topic question. Are you implementing GE as an instance of the GE over rings? If so, is it possible to formulate Unification and Type Inference for say STLC via your math library? Totally off topic. No is a fine answer. No. But it's on-topic, so you get a slightly longer answer. :D Because there's no generics support in Typed Racket, we're sticking to matrices of Real and Number for now. I'd love to have good typed generics for somewhat less esoteric things like polynomials, intervals, and the FFT, or for matrices with bigfloat elements. Neil ⊥ _ Racket Developers list: http://lists.racket-lang.org/dev
