GitHub

Linear solving

Overview of the functionality

The module AbstractAlgebra.Solve provides the following four functions for solving linear systems:

All of these take the same set of arguments, namely:

  • a matrix $A$ of type MatElem;
  • a vector or matrix $B$ of type Vector or MatElem;
  • a keyword argument side which can be either :left (default) or :right.

If side is :left, the system $xA = B$ is solved, otherwise the system $Ax = B$ is solved.

The functionality of the functions can be summarized as follows.

  • solve: return a solution, if it exists, otherwise throw an error.
  • can_solve: return true, if a solution exists, false otherwise.
  • can_solve_with_solution: return true and a solution, if this exists, and false and an empty vector or matrix otherwise.
  • can_solve_with_solution_and_kernel: like can_solve_with_solution and additionally return a matrix whose rows (respectively columns) give a basis of the kernel of $A$.

Furthermore, there is a function kernel which computes the kernel of a matrix $A$.

Solving with several right hand sides

Systems $xA = b_1,\dots, xA = b_k$ with the same matrix $A$, but several right hand sides $b_i$ can be solved more efficiently, by first initializing a "context object" C.

solve_init — Method
solve_init(A::MatElem)

Return a context object C that allows to efficiently solve linear systems $Ax = b$ or $xA = b$ for different $b$.

Example

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

julia> C = solve_init(A)
Linear solving context of matrix
  [1//1   2//1   3//1]
  [0//1   3//1   0//1]
  [5//1   0//1   0//1]

julia> solve(C, [QQ(1), QQ(1), QQ(1)]; side = :left)
3-element Vector{Rational{BigInt}}:
 1//3
 1//9
 2//15

julia> solve(C, [QQ(1), QQ(1), QQ(1)]; side = :right)
3-element Vector{Rational{BigInt}}:
 1//5
 1//3
 2//45
source

Now the functions solve, can_solve, etc. can be used with C in place of $A$. This way the time-consuming part of the solving (i.e. computing a reduced form of $A$) is only done once and the result cached in C to be reused.

Detailed documentation

solve — Method
solve(A::MatElem{T}, b::Vector{T}; side::Symbol = :left) where T
solve(A::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where T
solve(C::SolveCtx{T}, b::Vector{T}; side::Symbol = :left) where T
solve(C::SolveCtx{T}, b::MatElem{T}; side::Symbol = :left) where T

Return $x$ of same type as $b$ solving the linear system $xA = b$, if side == :left (default), or $Ax = b$, if side == :right.

If no solution exists, an error is raised.

If a context object C is supplied, then the above applies for A = matrix(C).

See also can_solve_with_solution.

Example

julia> A = QQ[2 0 0;0 3 0;0 0 5]
[2//1   0//1   0//1]
[0//1   3//1   0//1]
[0//1   0//1   5//1]

julia> solve(A, one(A))
[1//2   0//1   0//1]
[0//1   1//3   0//1]
[0//1   0//1   1//5]
source
can_solve — Method
can_solve(A::MatElem{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve(A::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where T
can_solve(C::SolveCtx{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve(C::SolveCtx{T}, b::MatElem{T}; side::Symbol = :left) where T

Return true if the linear system $xA = b$ or $Ax = b$ with side == :left (default) or side == :right, respectively, has a solution and false otherwise.

If a context object C is supplied, then the above applies for A = matrix(C).

See also can_solve_with_solution.

Example

julia> A = QQ[2 0 0;0 3 0;0 0 5]
[2//1   0//1   0//1]
[0//1   3//1   0//1]
[0//1   0//1   5//1]

julia> can_solve(A,one(A))
true

julia> A = ZZ[2 0 0;0 3 0;0 0 5]
[2   0   0]
[0   3   0]
[0   0   5]

julia> can_solve(A,one(A))
false
source
can_solve_with_solution — Method
can_solve_with_solution(A::MatElem{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve_with_solution(A::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where T
can_solve_with_solution(C::SolveCtx{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve_with_solution(C::SolveCtx{T}, b::MatElem{T}; side::Symbol = :left) where T

Return true and $x$ of same type as $b$ solving the linear system $xA = b$, if such a solution exists. Return false and an empty vector or matrix, if the system has no solution.

If side == :right, the system $Ax = b$ is solved.

If a context object C is supplied, then the above applies for A = matrix(C).

See also solve.

source
kernel — Method
kernel(A::MatElem; side::Symbol = :left)
kernel(C::SolveCtx; side::Symbol = :left)

Return a matrix $K$ whose rows generate the left kernel of $A$, that is, $KA$ is the zero matrix.

If side == :right, the columns of $K$ generate the right kernel of $A$, that is, $AK$ is the zero matrix.

If the base ring is a principal ideal domain, the rows or columns respectively of $K$ are a basis of the respective kernel.

If a context object C is supplied, then the above applies for A = matrix(C).

#Example

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

julia> kernel(A, side=:right)
[-3//1   0//1]
[ 1//1   0//1]
[ 0//1   0//1]
[ 0//1   1//1]

julia> kernel(A)
[-1//2   1//1   0//1]
source
can_solve_with_solution_and_kernel — Method
can_solve_with_solution_and_kernel(A::MatElem{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve_with_solution_and_kernel(A::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where T
can_solve_with_solution_and_kernel(C::SolveCtx{T}, b::Vector{T}; side::Symbol = :left) where T
can_solve_with_solution_and_kernel(C::SolveCtx{T}, b::MatElem{T}; side::Symbol = :left) where T

Return true, $x$ of same type as $b$ solving the linear system $xA = b$, together with a matrix $K$ giving the kernel of $A$ (i.e. $KA = 0$), if such a solution exists. Return false, an empty vector or matrix and an empty matrix, if the system has no solution.

If side == :right, the system $Ax = b$ is solved.

If a context object C is supplied, then the above applies for A = matrix(C).

See also solve and kernel.

source