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:

Status badges

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)

solve2.sage (1.1 KB) - added by rbeezer 10 years ago.

Download all attachments as: .zip

Change History (10)

Changed 10 years ago by rbeezer

comment:1 Changed 10 years ago by rbeezer

  • Authors set to Rob Beezer
  • Status changed from new to needs_info

comment:2 follow-up: Changed 10 years ago by 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.

comment:3 in reply to: ↑ 2 Changed 10 years ago by rbeezer

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 saliola

  • Keywords days30 added

comment:5 Changed 10 years ago by burcin

  • Cc burcin added

comment:6 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:7 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.