How to exactly solve large overdetermined systems of linear equations

Specific Domains Numerics
1

Suppose I have, e.g., 250 linear equations with Rational{BigInt} coefficients, with 150 variables. If the system is inconsistent I want to know about it, otherwise I want the exact solution.

Is there an easier way than writing my own Gaussian elimination?

This won’t run often, so I’m not concerned with long runtimes.

2

Have a look at Nemo.jl; it does exact linear algebra.

1 Like
3

Just for sake of completeness, either using AbstractAlgebra or (more efficiently) Nemo, it can be done as follows:

julia> using AbstractAlgebra # will also work with using Nemo;

julia> A = QQ[1 0; 3 0; 5 0]; # create an AbstractAlgebra matrix

julia> v = QQ[1; 2; 3]; # create a 3x1 matrix

julia> can_solve_with_solution(A, v) # solve Ax = v
(false, [1; 0])

julia> A = QQ[1 2; 3 4; 5 6];

julia> can_solve_with_solution(A, v) # solve Ax = v
(true, [0; 1//2])

julia> fl, x = can_solve_with_solution(A, v) # solve Ax = v
(true, [0; 1//2])

julia> A*x == v
true

One can also do can_solve_with_solution(A, v; side = :left) to solve xA = v.

1 Like
4

TBH I didn’t even realize that can_solve_with_solution existed, instead i used AbstractAlgebra.rref :sweat_smile: