`LinearSolveSequence`

Provides methods to solve linear systems over sequence rings.

class rec_sequences.LinearSolveSequence.LinearSolveSequence

Bases: object

Provides methods to solve linear systems over sequence rings. It is always assumed that the base ring satisfies the Skolem-Mahler-Lech Theorem.

classmethod clear_denominators(v, bound=100)

Clears the denominators of fractional sequences.

INPUT:

v – a (non-empty) vector or list of sequences in a rec_sequences.SequenceRingOfFraction.
bound (default: 100) – a natural number, used as the number of terms to guess a common multiple of the denominators of the sequences in v.

OUTPUT:

d and a list v*d such that d is a common multiple of the denominators of v.

EXAMPLES:

sage: from rec_sequences.LinearSolveSequence import *
sage: from rec_sequences.CFiniteSequenceRing import *
sage: from rec_sequences.SequenceRingOfFraction import *

sage: C = CFiniteSequenceRing(QQ)
sage: QC = SequenceRingOfFraction(C)
sage: d0 = C([2,0,-1], [1,-2])
sage: d1 = C([1,-2,1], [3,1])
sage: c0 = C([3,0,-1], [1,3])
sage: c1 = C([1,1,-1], [1,2])
sage: a = QC(c0, d0)
sage: b = QC(c1, d1)

sage: v = vector(QC, [a, b])
sage: d, cleared = LinearSolveSequence.clear_denominators(v, 10)
sage: d == d0*d1
True
sage: cleared_v = vector(C, cleared)
sage: v*d == cleared_v
True

classmethod clear_divisor(v, bound=50)

Given a vector of sequences \(v=(v_0,\dots,v_m)\) computes a common divisor \(d\) of \(v_0,\dots,v_m\). Tries guessing to find the gcd using bound number of values. If this fails, the common divisor \(1\) is returned. Assumes that \(m \geq 0\), i.e., \(v\) is non-empty.

INPUT:

v – a vector of sequences
bound (default: 50) – a natural number

OUTPUT:

A pair \(d\), divisors where \(d\) is a common divisor of all \(v_i\) and divisors is a list of sequences \(d_0,\dots,d_m\) with \(d_i d = v_i\) for all \(i\).

EXAMPLES:

sage: from rec_sequences.LinearSolveSequence import *
sage: from rec_sequences.CFiniteSequenceRing import *

sage: C = CFiniteSequenceRing(QQ)
sage: c1 = C([3,0,-1], [1,3])
sage: c2 = C([-1,1,1], [1,2])
sage: c3 = C([2,-1,1], [2,1])

sage: c = [c1*c2, c1*c3]
sage: d, div = LinearSolveSequence.clear_divisor(c, 10)
sage: d == c1
True
sage: d*div[0] == c[0], d*div[1] == c[1]
(True, True)

classmethod common_multiple(v, bound=100)

Given a vector of sequences \(v=(v_0,\dots,v_m)\) computes a common multiple \(d\) of \(v_0,\dots,v_m\). Tries guessing to find the lcm using bound number of values. If this fails, the product \(v_0 \cdots v_m\) is returned. Assumes that \(m \geq 0\), i.e., \(v\) is non-empty.

INPUT:

v – a vector of sequences
bound (default: 100) – a natural number

OUTPUT:

A pair \(d\), divisors where \(d\) is a common multiple of all \(v_i\) and divisors is a list of sequences \(d_0,\dots,d_m\) with \(d_i v_i = d\) for all \(i\).

EXAMPLES:

sage: from rec_sequences.LinearSolveSequence import *
sage: from rec_sequences.CFiniteSequenceRing import *

sage: C = CFiniteSequenceRing(QQ)
sage: c1 = C([3,0,-1], [1,3])
sage: c2 = C([1,1,-1], [1,2])

sage: d, div = LinearSolveSequence.common_multiple([c1*c2, c1], 10)
sage: d == c1*c2
True
sage: div[0]*c1*c2 == d, div[1]*c1 == d
(True, True)

log = <Logger LSS (WARNING)>

classmethod solve(M, b, guess=True, verified=False)

Tries to compute a solution \(x\) of the linear system

\[Mx=b.\]

Let R be the base ring. We assume that a sequence in R is invertible iff it does not have any zeros. If R is not a rec_sequences.SequenceRingOfFraction, the sequences are casted there and the system solved there.

INPUT:

M – the matrix of the linear system
b – the right-hand-side of the system
guess (default: True) – use guessing for solving the system
verified (default: False) – verify the result formally. If False the result might not (although unlikely) be a solution to the equation if guessing is used.

OUTPUT:

One possible solution \(x\) as a list if there is one. Otherwise, a ValueError is raised.

ALGORITHM:

The method implements the algorithm from Lemma 4.5 from [JPNP21b].

EXAMPLES:

sage: from rec_sequences.LinearSolveSequence import *
sage: from rec_sequences.CFiniteSequenceRing import *
sage: from rec_sequences.SequenceRingOfFraction import *

sage: C = CFiniteSequenceRing(QQ)
sage: QC = SequenceRingOfFraction(C)

sage: a = QC(C([3,0,-1], [1,3]), C([2,-1], [1]))
sage: b = QC(C([1,-1], [2]))
sage: c = QC(C([2,1], [3]))
sage: d = QC(C([1,1,-1], [1,2]), C([-2,1], [3]))
sage: v1 = vector(QC, [a,c])
sage: v2 = vector(QC, [b,d])
sage: M = matrix(QC, [v1, v2]).transpose()
sage: rhs = QC(C([3,1], [1]))*v1 \
....:       + QC(C([1,2,-1],[0,1]), C([2,-1], [2]))*v2
sage: x = vector(QC, LinearSolveSequence.solve(M, rhs))
sage: M*x==rhs
True

sage: a2 = C([3,0,-1], [1,3])
sage: b2 = C([1,-1], [2])
sage: c2 = C([2,1], [3])
sage: d2 = C([1,1,-1], [1,2])
sage: v12 = vector(C, [a2,c2])
sage: v22 = vector(C, [b2,d2])
sage: M2 = matrix(C, [v12, v22]).transpose()
sage: rhs2 = C([3,1], [1])*v12 + C([1,2,-1],[0,1])*v22
sage: x2 = vector(QC, LinearSolveSequence.solve(M2, rhs2, \
....:                                           guess=False))
sage: M2*x2==rhs2
True

sage: x3 = vector(QC, LinearSolveSequence.solve(M2, rhs2, \
....:                 guess=True, verified=True))
sage: M2*x3==rhs2
True