Linear solving
Overview of the functionality
The module AbstractAlgebra.Solve
provides the following four functions for solving linear systems:
solve
can_solve
can_solve_with_solution
can_solve_with_solution_and_kernel
All of these take the same set of arguments, namely:
- a matrix $A$ of type
MatElem
; - a vector or matrix $B$ of type
Vector
orMatElem
; - 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
: returntrue
, if a solution exists,false
otherwise.can_solve_with_solution
: returntrue
and a solution, if this exists, andfalse
and an empty vector or matrix otherwise.can_solve_with_solution_and_kernel
: likecan_solve_with_solution
and additionally return a matrix whose rows (respectively columns) give a basis of the kernel of $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
.
AbstractAlgebra.Solve.solve_init
— Functionsolve_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
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
AbstractAlgebra.Solve.solve
— Functionsolve(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
.
AbstractAlgebra.Solve.can_solve
— Functioncan_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
.
AbstractAlgebra.Solve.can_solve_with_solution
— Functioncan_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
.
AbstractAlgebra.Solve.can_solve_with_solution_and_kernel
— Functioncan_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)
.
AbstractAlgebra.kernel
— Functionkernel(f::ModuleHomomorphism{T}) where T <: RingElement
Return a pair K, g
consisting of the kernel object $K$ of the given module homomorphism $f$ (as a submodule of its domain) and the canonical injection from the kernel into the domain of $f$.
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)
.