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
.
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
solve
— FunctionOscar.solve(f::ZZPolyRingElem; max_prec::Int=typemax(Int))
Oscar.solve(f::QQPolyRingElem; max_prec::Int=typemax(Int))
Compute a presentation of the roots of f
in a radical tower. The necessary roots of unity are not themselves computed as radicals.
See also galois_group
.
VERBOSE
Supports set_verbosity_level(:SolveRadical, i)
to obtain information.
Examples
julia> Qx,x = QQ["x"];
julia> K, r = solve(x^3+3*x+5)
(Relative number field over with defining polynomial x^3 + (3*z_3 + 3//2)*a2 + 135//2
over Relative number field over with defining polynomial x^2 + 783
over Number field over Rational Field with defining polynomial x^2 + x + 1, Any[((1//81*z_3 + 1//162)*a2 - 5//18)*a3^2 + 1//3*a3, ((-1//162*z_3 + 1//162)*a2 + 5//18*z_3 + 5//18)*a3^2 + 1//3*z_3*a3, ((-1//162*z_3 - 1//81)*a2 - 5//18*z_3)*a3^2 + (-1//3*z_3 - 1//3)*a3])
julia> #z_3 indicates the 3-rd root-of-1 used
julia> map(x^3+3*x+5, r)
3-element Vector{Hecke.RelSimpleNumFieldElem{Hecke.RelSimpleNumFieldElem{AbsSimpleNumFieldElem}}}:
0
0
0
julia> solve(cyclotomic(12, x)) #zeta_12 as radical
(Relative number field over with defining polynomial x^2 - 3//4
over Number field over Rational Field with defining polynomial x^2 + 1, Any[a2 + 1//2*a1, a2 - 1//2*a1, -a2 - 1//2*a1, -a2 + 1//2*a1])
This function is part of the experimental code in Oscar. Please read here for more details.
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
.
can_solve
— Function can_solve(f::QuadBin, n::IntegerUnion) -> Bool
For a binary quadratic form f
with negative discriminant and an integer n
, return whether f
represents n
.
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
.
can_solve_with_solution
— Function can_solve_with_solution(f::QuadBin, n::IntegerUnion)
-> Bool, Tuple{ZZRingElem, ZZRingElem}
For a binary quadratic form f
with negative discriminant and an integer n
, return the tuple (true, (x, y))
if $f(x, y) = n$ for integers x
, y
. If no such integers exist, return (false, (0, 0))
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
.
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)
.
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(M::SMat{T}; side::Symbol = :left) where {T <: FieldElement}
Return a matrix $N$ containing a basis of the kernel of $M$. If side
is :left
(default), the left kernel is computed, i.e. the matrix of rows whose span gives the left kernel space. If side
is :right
, the right kernel is computed, i.e. the matrix of columns whose span is the right kernel space.
kernel(h::FinGenAbGroupHom) -> FinGenAbGroup, Map
Let $G$ be the domain of $h$. This function returns an abelian group $A$ and an injective morphism $f \colon A \to G$, such that the image of $f$ is the kernel of $h$.
kernel(f::TorQuadModuleMap) -> TorQuadModule, TorQuadModuleMap
Given an abelian group homomorphism f
between two torsion quadratic modules T
and U
, return the kernel S
of f
as well as the injection $S \to T$.
kernel(f::AbstractAlgebra.Map(SAlgHom))
Return the kernel of the algebra homomorphism $f$.
kernel(f::AbstractAlgebra.Map(SIdAlgHom))
Return the kernel of the identity algebra homomorphism.
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)
.
kernel(F::AffAlgHom)
Return the kernel of F
.
kernel(f::GAPGroupHomomorphism)
Return the kernel of f
, together with its embedding into domain
(f
).
kernel(chi::GAPGroupClassFunction)
Return C, f
where C
is the kernel of chi
(i.e. the largest normal subgroup of the underlying group G
of chi
such that chi
maps each element of C
to chi[1]
) and f
is the embedding morphism of C
into G
.
Examples
julia> t = character_table(symmetric_group(4));
julia> chi = t[3]; chi[1]
2
julia> C, f = kernel(chi); order(C)
4
kernel(a::FreeModuleHom)
Return the kernel of a
as an object of type SubquoModule
.
Additionally, if K
denotes this object, return the inclusion map K
$\to$ domain(a)
.
Examples
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])
julia> F = free_module(R, 3)
Free module of rank 3 over R
julia> G = free_module(R, 2)
Free module of rank 2 over R
julia> V = [y*G[1], x*G[1]+y*G[2], z*G[2]];
julia> a = hom(F, G, V);
julia> kernel(a)
(Submodule with 1 generator
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations., Map with following data
Domain:
=======
Submodule with 1 generator
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations.
Codomain:
=========
Free module of rank 3 over R)
julia> Rg, (x, y, z) = graded_polynomial_ring(QQ, ["x", "y", "z"]);
julia> F = graded_free_module(Rg, 3);
julia> G = graded_free_module(Rg, 2);
julia> V = [y*G[1], x*G[1]+y*G[2], z*G[2]];
julia> a = hom(F, G, V);
julia> kernel(a)
(Graded submodule of F
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations, Graded submodule of F
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations -> F
x*z*e[1] - y*z*e[2] + y^2*e[3] -> x*z*e[1] - y*z*e[2] + y^2*e[3]
Homogeneous module homomorphism)
kernel(a::SubQuoHom)
Return the kernel of a
as an object of type SubquoModule
.
Additionally, if K
denotes this object, return the inclusion map K
$\to$ domain(a)
.
kernel(a::ModuleFPHom)
Return the kernel of a
as an object of type SubquoModule
.
Additionally, if K
denotes this object, return the inclusion map K
$\to$ domain(a)
.
Examples
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> F = free_module(R, 3);
julia> G = free_module(R, 2);
julia> W = R[y 0; x y; 0 z]
[y 0]
[x y]
[0 z]
julia> a = hom(F, G, W);
julia> K, incl = kernel(a);
julia> K
Submodule with 1 generator
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations.
julia> incl
Map with following data
Domain:
=======
Submodule with 1 generator
1 -> x*z*e[1] - y*z*e[2] + y^2*e[3]
represented as subquotient with no relations.
Codomain:
=========
Free module of rank 3 over R
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> F = free_module(R, 1);
julia> A = R[x; y]
[x]
[y]
julia> B = R[x^2; y^3; z^4]
[x^2]
[y^3]
[z^4]
julia> M = SubquoModule(F, A, B)
Subquotient of Submodule with 2 generators
1 -> x*e[1]
2 -> y*e[1]
by Submodule with 3 generators
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
julia> N = M;
julia> V = [y^2*N[1], x*N[2]]
2-element Vector{SubquoModuleElem{QQMPolyRingElem}}:
x*y^2*e[1]
x*y*e[1]
julia> a = hom(M, N, V);
julia> K, incl = kernel(a);
julia> K
Subquotient of Submodule with 3 generators
1 -> (-x + y^2)*e[1]
2 -> x*y*e[1]
3 -> -x*y*e[1]
by Submodule with 3 generators
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
julia> incl
Map with following data
Domain:
=======
Subquotient of Submodule with 3 generators
1 -> (-x + y^2)*e[1]
2 -> x*y*e[1]
3 -> -x*y*e[1]
by Submodule with 3 generators
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
Codomain:
=========
Subquotient of Submodule with 2 generators
1 -> x*e[1]
2 -> y*e[1]
by Submodule with 3 generators
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
julia> Rg, (x, y, z) = graded_polynomial_ring(QQ, ["x", "y", "z"]);
julia> F = graded_free_module(Rg, 1);
julia> A = Rg[x; y];
julia> B = Rg[x^2; y^3; z^4];
julia> M = SubquoModule(F, A, B)
Graded subquotient of submodule of F generated by
1 -> x*e[1]
2 -> y*e[1]
by submodule of F generated by
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1]
julia> N = M;
julia> V = [y^2*N[1], x^2*N[2]];
julia> a = hom(M, N, V)
M -> M
x*e[1] -> x*y^2*e[1]
y*e[1] -> x^2*y*e[1]
Graded module homomorphism of degree [2]
julia> kernel(a)
(Graded subquotient of submodule of F generated by
1 -> y*e[1]
2 -> -x*y*e[1]
by submodule of F generated by
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1], Graded subquotient of submodule of F generated by
1 -> y*e[1]
2 -> -x*y*e[1]
by submodule of F generated by
1 -> x^2*e[1]
2 -> y^3*e[1]
3 -> z^4*e[1] -> M
y*e[1] -> y*e[1]
-x*y*e[1] -> -x*y*e[1]
Homogeneous module homomorphism)
kernel(h::LieAlgebraHom) -> LieAlgebraIdeal
Return the kernel of h
as an ideal of the domain.
This function is part of the experimental code in Oscar. Please read here for more details.