Opened 10 years ago
Last modified 7 years ago
#11286 needs_info enhancement
Speed-up solving linear systems
Reported by: | rbeezer | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | linear algebra | Keywords: | days30 |
Cc: | burcin | Merged in: | |
Authors: | Rob Beezer | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Patch implements solving a linear system of equations in the most naive way possible, just augmenting the matrix and row-reducing.
For fields like ZZ
, QQ
, and integers mod p, this can be 3% to 10% faster. For fields that use echelon form to get rank, this can be twice as fast since we only row-reduce once, not twice. Matrices full of integers mod p can be a toss-up as the number of columns in the constant matrix is about 10 times greater than for the coefficient matrix.
Timings below and script that produced them is attached.
This has the old doctests, which pass with the new method (except two trivial failures). Old method is included as solve_left_old()
for ease of testing timings. This is fully functional, but will need just a bit more work to be ready, so this is up for comments and suggestions at the moment.
Field: Integer Ring Rows: 100 Cols (coeffs) 100 Cols (constants) 1 Old: 15 loops, best of 2: 30.659 ms per loop New: 15 loops, best of 2: 26.411 ms per loop Rows: 100 Cols (coeffs) 500 Cols (constants) 1 Old: 15 loops, best of 2: 1.3159 s per loop New: 15 loops, best of 2: 1.3377 s per loop Rows: 100 Cols (coeffs) 100 Cols (constants) 1000 Old: 15 loops, best of 2: 3.3781 s per loop New: 15 loops, best of 2: 3.3435 s per loop Rows: 100 Cols (coeffs) 300 Cols (constants) 200 Old: 15 loops, best of 2: 1.7518 s per loop New: 15 loops, best of 2: 1.346 s per loop ************************** Field: Rational Field Rows: 100 Cols (coeffs) 100 Cols (constants) 1 Old: 15 loops, best of 2: 23.646 ms per loop New: 15 loops, best of 2: 18.902 ms per loop Rows: 100 Cols (coeffs) 500 Cols (constants) 1 Old: 15 loops, best of 2: 1.0791 s per loop New: 15 loops, best of 2: 1.0609 s per loop Rows: 100 Cols (coeffs) 100 Cols (constants) 1000 Old: 15 loops, best of 2: 2.8108 s per loop New: 15 loops, best of 2: 2.7389 s per loop Rows: 100 Cols (coeffs) 300 Cols (constants) 200 Old: 15 loops, best of 2: 1.3419 s per loop New: 15 loops, best of 2: 1.0658 s per loop ************************** Field: Ring of integers modulo 6337 Rows: 150 Cols (coeffs) 150 Cols (constants) 1 Old: 15 loops, best of 2: 30.246 ms per loop New: 15 loops, best of 2: 27.992 ms per loop Rows: 150 Cols (coeffs) 750 Cols (constants) 1 Old: 15 loops, best of 2: 131.07 ms per loop New: 15 loops, best of 2: 143 ms per loop Rows: 150 Cols (coeffs) 150 Cols (constants) 1500 Old: 15 loops, best of 2: 585.01 ms per loop New: 15 loops, best of 2: 636.57 ms per loop Rows: 150 Cols (coeffs) 450 Cols (constants) 300 Old: 15 loops, best of 2: 479.46 ms per loop New: 15 loops, best of 2: 204.56 ms per loop ************************** Field: Finite Field in a of size 5^4 Rows: 50 Cols (coeffs) 50 Cols (constants) 1 Old: 15 loops, best of 2: 35.873 ms per loop New: 15 loops, best of 2: 17.424 ms per loop Rows: 50 Cols (coeffs) 250 Cols (constants) 1 Old: 15 loops, best of 2: 179.94 ms per loop New: 15 loops, best of 2: 139.05 ms per loop Rows: 50 Cols (coeffs) 50 Cols (constants) 500 Old: 15 loops, best of 2: 346.74 ms per loop New: 15 loops, best of 2: 339.3 ms per loop Rows: 50 Cols (coeffs) 150 Cols (constants) 100 Old: 15 loops, best of 2: 360.61 ms per loop New: 15 loops, best of 2: 139.35 ms per loop **************************
Attachments (1)
Change History (10)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Status changed from new to needs_info
comment:2 follow-up: ↓ 3 Changed 10 years ago by
comment:3 in reply to: ↑ 2 Changed 10 years ago by
Replying to dimpase:
For QQ and other infinite exact fields, naive Gauss elimination is not a good strategy all together, as it can lead to an exponential blowup of coefficients.
Hi Dima!
Agreed. This is part of the challenge in testing this. But I believe this is the current strategy. In other words, eventually Sage does echelon form, with or without this patch.
QQ gets converted to ZZ, and I do not know if the routines over ZZ control for this. But when I test with matrices containing number fields (cyclotomics), the rational coefficients do get out of hand.
So this patch is an incremental improvement. With or without, we still rely on Gaussian elimination in 100% of cases (or nearly so).
Rob
comment:4 Changed 10 years ago by
- Keywords days30 added
comment:5 Changed 10 years ago by
- Cc burcin added
comment:6 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:7 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:8 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:9 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
For QQ and other infinite exact fields, naive Gauss elimination is not a good strategy all together, as it can lead to an exponential blowup of coefficients.