Ring functionality
AbstractAlgebra has both commutative and noncommutative rings. Together we refer to them below as rings.
Abstract types for rings
All commutative ring types in AbstractAlgebra belong to the Ring abstract type and commutative ring elements belong to the RingElem abstract type.
Noncommutative ring types belong to the NCRing abstract type and their elements to NCRingElem.
As Julia types cannot belong to our RingElem type hierarchy, we also provide the union type RingElement which includes RingElem in union with the Julia types Integer, Rational and AbstractFloat.
Similarly NCRingElement includes the Julia types just mentioned in union with NCRingElem.
Note that
Ring <: NCRing
RingElem <: NCRingElem
RingElement <: NCRingElementFunctions for types and parents of rings
parent_type(::Type{T}) where T <: NCRingElement
elem_type(::Type{T}) where T <: NCRingReturn the type of the parent (resp. element) type corresponding to the given ring element (resp. parent) type.
base_ring(R::NCRing)
base_ring(a::NCRingElement)For generic ring constructions over a base ring (e.g. polynomials over a coefficient ring), return the parent object of that base ring.
parent(a::NCRingElement)Return the parent of the given ring element.
is_domain_type(::Type{T}) where T <: NCRingElement
is_exact_type(::Type{T}) where T <: NCRingElementReturn true if the given ring element type can only belong to elements of an integral domain or exact ring respectively. (An exact ring is one whose elements are represented exactly in the system without approximation.)
The following function is implemented where mathematically and algorithmically possible.
characteristic(R::NCRing)Constructors
If R is a parent object of a ring in AbstractAlgebra, it can always be used to construct certain objects in that ring.
(R::NCRing)() # constructs zero
(R::NCRing)(c::Integer)
(R::NCRing)(c::elem_type(R))
(R::NCRing{T})(a::T) where T <: RingElementBasic functions
All rings in AbstractAlgebra are expected to implement basic ring operations, unary minus, binary addition, subtraction and multiplication, equality testing, powering.
In addition, the following are implemented for parents/elements just as they would be in Julia for types/objects.
zero(R::NCRing)
one(R::NCRing)
iszero(a::NCRingElement)
isone(a::NCRingElement)In addition, the following are implemented where it is mathematically/algorithmically viable to do so.
is_unit(a::NCRingElement)
is_zero_divisor(a::NCRingElement)
is_zero_divisor_with_annihilator(a::NCRingElement)The following standard Julia functions are also implemented for all ring elements.
hash(f::RingElement, h::UInt)
deepcopy_internal(a::RingElement, dict::IdDict)
show(io::IO, R::NCRing)
show(io::IO, a::NCRingElement)Basic functionality for inexact rings only
By default, inexact ring elements in AbstractAlgebra compare equal if they are the same to the minimum precision of the two elements. However, we also provide the following more strict notion of equality, which also requires the precisions to be the same.
isequal(a::T, b::T) where T <: NCRingElementFor floating point and ball arithmetic it is sometimes useful to be able to check if two elements are approximately equal, e.g. to suppress numerical noise in comparisons. For this, the following are provided.
isapprox(a::T, b::T; atol::Real=sqrt(eps())) where T <: RingElementSimilarly, for a parameterised ring with type MyElem{T} over such an inexact ring we have the following.
isapprox(a::MyElem{T}, b::T; atol::Real=sqrt(eps())) where T <: RingElement
isapprox(a::T, b::MyElem{T}; atol::Real=sqrt(eps())) where T <: RingElementThese notionally perform a coercion into the parameterised ring before doing the approximate equality test.
Basic functionality for commutative rings only
divexact(a::T, b::T) where T <: RingElement
inv(a::T)Return a/b or 1/a respectively, where the slash here refers to the mathematical notion of division in the ring, not Julia's floating point division operator.
Basic functionality for noncommutative rings only
divexact_left(a::T, b::T) where T <: NCRingElement
divexact_right(a::T, b::T) where T <: NCRingElementAs per divexact above, except that division by b happens on the left or right, respectively, of a.
Unsafe ring operators
To speed up polynomial and matrix arithmetic, it sometimes makes sense to mutate values in place rather than replace them with a newly created object every time they are modified.
For this purpose, certain mutating operators are required. In order to support immutable types (struct in Julia) and systems that don't have in-place operators, all unsafe operators must return the (ostensibly) mutated value. Only the returned value is used in computations, so this lifts the requirement that the unsafe operators actually mutate the value.
Note the exclamation point is a convention, which indicates that the object may be mutated in-place.
To make use of these functions, one must be certain that no other references are held to the object being mutated, otherwise those values will also be changed!
The results of deepcopy and all arithmetic operations, including powering and division can be assumed to be new objects without other references being held, as can objects returned from constructors.
It is important to recognise that R(a) where R is the ring a belongs to, does not create a new value. For this case, use deepcopy(a).
zero! — Functionzero!(a)Return zero(parent(a)), possibly modifying the object a in the process.
one! — Functionone!(a)Return one(parent(a)), possibly modifying the object a in the process.
add! — Functionadd!(z, a, b)
add!(a, b)Return a + b, possibly modifying the object z in the process. Aliasing is permitted. The two argument version is a shorthand for add!(a, a, b).
sub! — Functionsub!(z, a, b)
sub!(a, b)Return a - b, possibly modifying the object z in the process. Aliasing is permitted. The two argument version is a shorthand for sub!(a, a, b).
mul! — Functionmul!(z, a, b)
mul!(a, b)Return a * b, possibly modifying the object z in the process. Aliasing is permitted. The two argument version is a shorthand for mul!(a, a, b).
neg! — Functionneg!(z, a)
neg!(a)Return -a, possibly modifying the object z in the process. Aliasing is permitted. The unary version is a shorthand for neg!(a, a).
inv! — Functioninv!(z, a)
inv!(a)Return AbstractAlgebra.inv(a), possibly modifying the object z in the process. Aliasing is permitted. The unary version is a shorthand for inv!(a, a).
AbstractAlgebra.inv and Base.inv differ only in their behavior on julia types like Integer and Rational{Int}. The former makes it adhere to the Ring interface.
addmul! — Functionaddmul!(z, a, b, t)
addmul!(z, a, b)Return z + a * b, possibly modifying the objects z and t in the process.
The second version is usually a shorthand for addmul!(z, a, b, parent(z)()), but in some cases may be more efficient. For multiple operations in a row that use temporary storage, it is still best to use the four argument version.
submul! — Functionsubmul!(z, a, b, t)
submul!(z, a, b)Return z - a * b, possibly modifying the objects z and t in the process.
The second version is usually a shorthand for submul!(z, a, b, parent(z)()), but in some cases may be more efficient. For multiple operations in a row that use temporary storage, it is still best to use the four argument version.
divexact! — Functiondivexact!(A::Generic.Mat{AbsSimpleNumFieldElem}, p::ZZRingElem)Inplace: divide each entry of $A$ by $p$.
divexact!(z, a, b)
divexact!(a, b)Return divexact(a, b), possibly modifying the object z in the process. Aliasing is permitted. The two argument version is a shorthand for divexact(a, a, b).
div! — Functiondiv!(z, a, b)
div!(a, b)Return div(a, b), possibly modifying the object z in the process. Aliasing is permitted. The two argument version is a shorthand for div(a, a, b).
AbstractAlgebra.div and Base.div differ only in their behavior on julia types like Integer and Rational{Int}. The former makes it adhere to the Ring interface.
rem! — Functionrem!(z, a, b)
rem!(a, b)Return rem(a, b), possibly modifying the object z in the process. Aliasing is permitted. The two argument version is a shorthand for rem(a, a, b).
mod! — Functionmod!(M::ZZMatrix, p::ZZRingElem)Reduces every entry modulo $p$ in-place, i.e. applies the mod function to every entry. Positive residue system.
mod!(A::Generic.Mat{AbsSimpleNumFieldElem}, m::ZZRingElem)Inplace: reduce all entries of $A$ modulo $m$, into the positive residue system.
mod!(z, a, b)
mod!(a, b)Return mod(a, b), possibly modifying the object z in the process. Aliasing is permitted. The two argument version is a shorthand for mod(a, a, b).
mod!(A::SRow{ZZRingElem}, n::Integer) -> SRow{ZZRingElem}Inplace reduction of all entries of $A$ modulo $n$ to the positive residue system.
mod!(A::SRow{ZZRingElem}, n::ZZRingElem) -> SRow{ZZRingElem}Inplace reduction of all entries of $A$ modulo $n$ to the positive residue system.
gcd! — Functiongcd!(z, a, b)
gcd!(a, b)Return gcd(a, b), possibly modifying the object z in the process. Aliasing is permitted. The two argument version is a shorthand for gcd(a, a, b).
lcm! — Functionlcm!(z, a, b)
lcm!(a, b)Return lcm(a, b), possibly modifying the object z in the process. Aliasing is permitted. The two argument version is a shorthand for lcm(a, a, b).
Random generation
The Julia random interface is implemented for all ring parents (instead of for types). The exact interface differs depending on the ring, but the parameters supplied are usually ranges, e.g. -1:10 for the range of allowed degrees for a univariate polynomial.
rand(R::NCRing, v...)Factorization
For commutative rings supporting factorization and irreducibility testing, the following optional functions may be implemented.
is_irreducible — Methodis_irreducible(a::RingElement)Return true if $a$ is irreducible, else return false. Zero and units are by definition never irreducible.
is_squarefree — Methodis_squarefree(a::RingElement)Return true if $a$ is squarefree, else return false. An element is squarefree if it it is not divisible by any squares except the squares of units.
factor(a::T) where T <: RingElement
factor_squarefree(a::T) where T <: RingElementReturn a factorization into irreducible or squarefree elements, respectively. The return is an object of type Fac{T}.
Fac — TypeFac{T <: RingElement}Type for factored ring elements. The structure holds a unit of type T and is an iterable collection of T => Int pairs for the factors and exponents.
See unit(a::Fac), evaluate(a::Fac).
unit — Methodunit(a::Fac{T}) -> TReturn the unit of the factorization.
evaluate — Methodevaluate(a::Fac{T}) -> TMultiply out the factorization into a single element.
getindex — Methodgetindex(a::Fac, b) -> IntIf $b$ is a factor of $a$, the corresponding exponent is returned. Otherwise an error is thrown.
setindex! — Methodsetindex!(a::Fac{T}, c::Int, b::T)If $b$ is a factor of $a$, the corresponding entry is set to $c$.