GitHub

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 <: NCRingElement

Functions for types and parents of rings

parent_type(::Type{T}) where T <: NCRingElement
elem_type(::Type{T}) where T <: NCRing

Return 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 <: NCRingElement

Return 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 <: RingElement

Basic 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 <: NCRingElement

For 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 <: RingElement

Similarly, 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 <: RingElement

These 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 <: NCRingElement

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

Note

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

AbstractAlgebra.add! — Function
add!(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).

source
AbstractAlgebra.sub! — Function
sub!(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).

source
AbstractAlgebra.mul! — Function
mul!(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).

source
AbstractAlgebra.neg! — Function
neg!(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).

source
AbstractAlgebra.inv! — Function
inv!(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).

Note

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.

source
AbstractAlgebra.addmul! — Function
addmul!(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.

source
AbstractAlgebra.submul! — Function
submul!(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.

source
AbstractAlgebra.divexact! — Function
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).

source
AbstractAlgebra.div! — Function
div!(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).

Note

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.

source
AbstractAlgebra.rem! — Function
rem!(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).

source
AbstractAlgebra.mod! — Function
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).

source
AbstractAlgebra.gcd! — Function
gcd!(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).

source
AbstractAlgebra.lcm! — Function
lcm!(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).

source

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.

AbstractAlgebra.is_irreducible — Method
is_irreducible(a::RingElement)

Return true if $a$ is irreducible, else return false. Zero and units are by definition never irreducible.

source
AbstractAlgebra.is_squarefree — Method
is_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.

source
factor(a::T) where T <: RingElement
factor_squarefree(a::T) where T <: RingElement

Return a factorization into irreducible or squarefree elements, respectively. The return is an object of type Fac{T}.

Base.getindex — Method
getindex(a::Fac, b) -> Int

If $b$ is a factor of $a$, the corresponding exponent is returned. Otherwise an error is thrown.

source
Base.setindex! — Method
setindex!(a::Fac{T}, c::Int, b::T)

If $b$ is a factor of $a$, the corresponding entry is set to $c$.

source