|
Size: 1004
Comment:
|
← Revision 17 as of 2008-11-14 13:41:58 ⇥
Size: 2528
Comment: converted to 1.6 markup
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 2: | Line 2: |
| == Tasks == | |
| Line 3: | Line 4: |
| == Issues to address == | * Finish writing sage/matrix/benchmark.py * Create some modular symbols benchmarks. * Sparse matrices over QQ (fast). * Basic matrix arithmetic speed ups: * copy, compare, negation, etc. * Fix bugs in linbox so SAGE can use linbox charpoly, etc., etc. * Fix bugs in multimodular matrix multiply on 64-bit machines. * ASAP -- Option to disable all use of linbox (and do this by default for now) -- it's buggy on meccah (try det there in matrix_integer_dense). We need way more work before rolling this out by default in *any* cases! * Investigate using envelopes with linbox. |
| Line 5: | Line 14: |
| * Robert Bradshaw implemented multimodular matrix multiply over ZZ. 1. This seems to work fine on 32-bit machines, but is totally broken on 64-bit machines, so is currently disabled (in sage-2.1.2). |
== Notes == [[LinBox/LinBox| tips for using Linbox]] == Benchmarks == From sage-2.1.2 do {{{ import sage.matrix.benchmark as b b.[tab] }}} to see some of the benchmarks that we would like to optimize. Currently exact linear algebra in SAGE is still, in some cases, a serious embarrassment. == Matrix multiplication over ZZ == Robert Bradshaw implemented multimodular matrix multiply over ZZ. 1. This seems to work fine on 32-bit machines --(but is totally broken on 64-bit machines, so is currently disabled (in sage-2.1.2))-- and works on 64-bit machines. |
| Line 8: | Line 32: |
| 3. Why is this so much '''slower''' than linbox? | 3. Why is this so much '''slower''' in linbox? |
| Line 11: | Line 35: |
| * Linbox: Charpoly and minpoly over ZZ. 1. They hang on 32-bit Debian Linux and on sage.math, so are disabled in the sage-2.1.2. |
== Charpoly and minpoly over ZZ == |
| Line 14: | Line 37: |
| == Benchmarks to help direct our work == | The linbox versions *sometimes* hang on 32-bit Debian Linux 9with libgslcblas) and on sage.math, so are disabled in the sage-2.1.2. The seem to work perfectly on OS X and other LInux installs. |
| Line 16: | Line 39: |
| === New code written from scratch in C/SageX/Python === | === Smith Normal Form === The SmithForm (or invariant factors) algorithm, which gives the invariant factors, is literally a hundred times slower than MAGMA. It's even slower than PARI for small n. |
| Line 20: | Line 46: |
| === Linbox === | This has optimized dense echelon form over finite fields and a very fast implementation of the p-adic nullspace algorithm (which is very useful for echelon forms over QQ!). Problems: |
| Line 22: | Line 48: |
| The SmithForm (or invariant factors) algorithm, which gives the invariant factors, is literally a hundred times slower than MAGMA. | 1. the p-adic nullspace algorithm is only implemented for matrices whose entries are C long's. But looking at the source code very strongly suggests it could easily be extended to the general case. 2. IML currently depends on atlas, so we have to rewrite it so it doesn't. This is probably not too hard. |
William Stein: Optimized exact sparse and dense linear algebra (especially for computing modular forms)
Tasks
- Finish writing sage/matrix/benchmark.py
- Create some modular symbols benchmarks.
- Sparse matrices over QQ (fast).
- Basic matrix arithmetic speed ups:
- copy, compare, negation, etc.
- Fix bugs in linbox so SAGE can use linbox charpoly, etc., etc.
- Fix bugs in multimodular matrix multiply on 64-bit machines.
- ASAP -- Option to disable all use of linbox (and do this by default for now) -- it's buggy on meccah (try det there in matrix_integer_dense). We need way more work before rolling this out by default in *any* cases!
- Investigate using envelopes with linbox.
Notes
Benchmarks
From sage-2.1.2 do
import sage.matrix.benchmark as b b.[tab]
to see some of the benchmarks that we would like to optimize. Currently exact linear algebra in SAGE is still, in some cases, a serious embarrassment.
Matrix multiplication over ZZ
Robert Bradshaw implemented multimodular matrix multiply over ZZ.
This seems to work fine on 32-bit machines but is totally broken on 64-bit machines, so is currently disabled (in sage-2.1.2) and works on 64-bit machines.
- It is interesting to fine tune the algorithm, and decide when to switch over to a multimodular method.
Why is this so much slower in linbox?
- Why is it slower than MAGMA? (How much slower?)
Charpoly and minpoly over ZZ
The linbox versions *sometimes* hang on 32-bit Debian Linux 9with libgslcblas) and on sage.math, so are disabled in the sage-2.1.2. The seem to work perfectly on OS X and other LInux installs.
Smith Normal Form
The SmithForm (or invariant factors) algorithm, which gives the invariant factors, is literally a hundred times slower than MAGMA. It's even slower than PARI for small n.
IML -- Integer Matrix Library
This has optimized dense echelon form over finite fields and a very fast implementation of the p-adic nullspace algorithm (which is very useful for echelon forms over QQ!). Problems:
- the p-adic nullspace algorithm is only implemented for matrices whose entries are C long's. But looking at the source code very strongly suggests it could easily be extended to the general case.
- IML currently depends on atlas, so we have to rewrite it so it doesn't. This is probably not too hard.