New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Speed-up solving linear systems #11286
Comments
Attachment: solve2.sage.gz |
Author: Rob Beezer |
comment:2
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. |
comment:3
Replying to @dimpase:
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 |
Changed keywords from none to days30 |
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.CC: @burcin
Component: linear algebra
Keywords: days30
Author: Rob Beezer
Issue created by migration from https://trac.sagemath.org/ticket/11286
The text was updated successfully, but these errors were encountered: