How to exactly solve large overdetermined systems of linear equations

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.

1 Like

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

2 Likes

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`.

2 Likes

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

hello thofma,
this interests me very much. does a QQMatrix has some elements of the type BigInt ? I want to solve a very big system A.X=Y with Rational{BigInt}. Thanks !
And, is there a fast way to convert a Matrix{Rational{BigInt}} to a QQMatrix, and back ? I could copy it term by term, eventually …

thanks a lot

Yes, there is a fast way. Here is an example, where one solves `A*X = Y` where `X` and `Y` are of type `Vector`.

``````julia> AA = Rational{BigInt}[1 2; 3 4]
2×2 Matrix{Rational{BigInt}}:
1  2
3  4

julia> A = matrix(QQ, AA)
[1   2]
[3   4]

julia> YY = Rational{BigInt}[5, 6]
2-element Vector{Rational{BigInt}}:
5
6

julia> Y = QQ.(YY)
2-element Vector{QQFieldElem}:
5
6

julia> fl, X = can_solve_with_solution(A, Y; side = :right) # solves A * X = Y for X
(true, QQFieldElem[-4, 9//2])

julia> Rational{BigInt}.(X)
2-element Vector{Rational{BigInt}}:
-4
9//2
``````

Here is an example, where `X` and `Y` are themselves of type `Matrix`:

``````julia> YY = Rational{BigInt}[5 6; 7 8]
2×2 Matrix{Rational{BigInt}}:
5  6
7  8

julia> Y = matrix(QQ, YY)
[5   6]
[7   8]

julia> fl, X = can_solve_with_solution(A, Y; side = :right) # solves A * X = Y for X
(true, [-3 -4; 4 5])

julia> XX = Matrix{Rational{BigInt}}(X)
2×2 Matrix{Rational{BigInt}}:
-3  -4
4   5
``````

Depending on how what you mean with “very big”, it might take a while to solve your system, but give it a try!

Ok thanks, everything works well I am new to Julia, and I don’t understand “constructors” well !

“Big Matrix” means only that I might need some BigInt, in any case the coefficients explode

Thanks a lot !
Gustave

Hello
I actually I should use Matrix{Complex{Rational{Int}}} . Is there way to do so with Nemo ? Or maybe with AbstractAlgebra ? Thanks !

finally I did the code with Complex{Float64}. But I like Algebra, so that your answer interests me !!!
Bye

Sorry for the late reply. Yes, this is also possible:

``````julia> QQi = Nemo.QQiField()
Gaussian rational field

julia> AA = Complex{Rational{BigInt}}[1 2im; 3 4im]
2×2 Matrix{Complex{Rational{BigInt}}}:
1//1+0//1*im  0//1+2//1*im
3//1+0//1*im  0//1+4//1*im

julia> A = matrix(QQi, AA)
[1   2*im]
[3   4*im]

julia> YY = Complex{Rational{BigInt}}[5im, 6]
2-element Vector{Complex{Rational{BigInt}}}:
0//1 + 5//1*im
6//1 + 0//1*im

julia> Y = QQi.(YY)
2-element Vector{Nemo.QQiFieldElem}:
5*im
6

julia> fl, X = can_solve_with_solution(A, Y; side = :right) # solves A * X = Y for X
(true, Nemo.QQiFieldElem[6 - 10*im, 15//2 + 3*im])

julia> XX = [Complex{Rational{BigInt}}(real(y), imag(y)) for y in X]
2-element Vector{Complex{Rational{BigInt}}}:
6//1 - 10//1*im
15//2 + 3//1*im
``````

OK thanks, it’s perfect ! I gonna try it tomorrow
Have a nice day
Gustave

It works perfectly well, thank you !!!