vectors_in_intervals.linear_inequality_systems

Linear inequality systems

EXAMPLES:

sage: from vectors_in_intervals import *
sage: A = matrix([[1, 2], [0, 1]])
sage: B = matrix([[2, 3]])
sage: C = matrix([[-1, 0]])
sage: S = HomogeneousSystem(A, B, C)
sage: S.solve()
(0, 1)
sage: S.certify_existence()
(2, 1, 3, 0)
sage: S.certify_nonexistence()
Traceback (most recent call last):
...
ValueError: A solution exists!
sage: S.certify()
(True, (2, 1, 3, 0))
sage: S.certify(reverse=True)
(True, (2, 1, 3, 0))
sage: S.certify_parallel()
(True, (2, 1, 3, 0))
sage: S.certify_parallel(reverse=True)
(True, (2, 1, 3, 0))
sage: S.certify_parallel(random=True)
(True, (2, 1, 3, 0))

We consider another system:

sage: M = matrix([[1, 0], [0, 1], [1, 1], [0, 1]])
sage: lower_bounds = [2, 5, 0, -oo]
sage: upper_bounds = [5, oo, 8, 5]
sage: lower_bounds_closed = [True, True, False, False]
sage: upper_bounds_closed = [False, False, False, True]
sage: I = intervals_from_bounds(lower_bounds, upper_bounds, lower_bounds_closed, upper_bounds_closed)
sage: S = LinearInequalitySystem(M, I)
sage: S.solve()
(2, 5)
sage: S.certify_existence()
(3, 7, 1, 1, 0, 0, 0)
sage: S.certify()
(True, (3, 7, 1, 1, 0, 0, 0))
sage: S.certify(reverse=True)
(True, (5, 15, 1, 2, 1, 0, 0))
sage: # S.certify_parallel() # TODO SignalError: Segmentation Fault
(True, (3, 7, 1, 1, 0, 0, 0))

We consider yet another system:

sage: A = matrix([[1, 0], [1, 1]])
sage: B = matrix([[-1, -1]])
sage: b = vector([1, 0])
sage: c = vector([0])
sage: S = InhomogeneousSystem(A, B, b, c)
sage: S.certify()
(False, (0, 1, 1))
sage: S.certify_parallel()
(False, (0, 1, 1))
sage: S.certify_parallel(random=True)
(False, (0, 1, 1))

In the case of homogeneous systems, we can use cocircuits to certify:

sage: A = matrix([[1, 2], [0, 1]])
sage: B = matrix([[2, 3]])
sage: C = matrix([[-1, 0]])
sage: S = HomogeneousSystemCocircuits(A, B, C)
sage: S.solve()
Traceback (most recent call last):
...
ValueError: Can't solve using cocircuits!
sage: S.certify_existence()
(+++0)
sage: # S.certify() # TODO

We consider another example:

sage: A = matrix([[1, 0], [0, 1]])
sage: B = matrix([[2, -3]])
sage: C = matrix([[-1, -1]])
sage: S = HomogeneousSystemCocircuits(A, B, C)
sage: S.certify_nonexistence()
(++0+)

Functions

homogeneous_from_general(system)	Convert a general system to a homogeneous system.
homogeneous_from_inhomogeneous(system)	Convert an inhomogeneous system to a homogeneous system.
inhomogeneous_from_general(system)	Translate a general system into an inhomogeneous system.

Classes

HomogeneousSystem(A, B, C[, result])	A class for homogeneous linear inequality systems
HomogeneousSystemCocircuits(A, B, C[, result])	A class for homogeneous linear inequality systems
InhomogeneousSystem(A, B, b, c[, result])	A class for inhomogeneous linear inequality systems
LinearInequalitySystem(_matrix, intervals[, ...])	A class for linear inequality systems given by a matrix and intervals

class vectors_in_intervals.linear_inequality_systems.HomogeneousSystem(A, B, C, result=None)

A class for homogeneous linear inequality systems

A x > 0, B x >= 0, C x = 0

TESTS:

sage: from vectors_in_intervals import *
sage: A = matrix([[0, 1], [0, 1], [0, 1]])
sage: B = zero_matrix(0, 2)
sage: C = matrix([[1, 1], [0, 0]])
sage: S = HomogeneousSystem(A, B, C)
sage: S.certify_existence()
(1, 1, 1, 0, 0)

certify_existence(reverse: bool = False, random: bool = False)

Certify existence of a solution if one exists.

Otherwise, a ValueError is raised.

Note

If a solution exists and random is set to true, this method will never finish.

exists_orthogonal_vector(v) → bool

Check if an orthogonal vector exists in the intervals.

get_intervals() → list

Return the corresponding intervals.

solve(reverse: bool = False, random: bool = False)

Compute a solution if existent.

This approach sums up positive elementary vectors in the row space. It doesn’t use division.

Note

If no solution exists, and random is true, this method will never finish.

to_homogeneous()

Return the equivalent homogeneous system.

class vectors_in_intervals.linear_inequality_systems.HomogeneousSystemCocircuits(A, B, C, result=None)

A class for homogeneous linear inequality systems

A x > 0, B x >= 0, C x = 0

Certifying makes use of cocircuits instead of elementary vectors

certify_existence(reverse: bool = False, random: bool = False) → sign_vectors.sign_vectors.SignVector

Compute a solution if existent.

This approach sums up positive elementary vectors in the row space.

Note

If no solution exists, and random is true, this method will never finish.

exists_orthogonal_vector(v) → bool

Check if an orthogonal vector exists in the intervals.

solve(reverse: bool = False, random: bool = False)

Compute a solution if existent.

This approach sums up positive elementary vectors in the row space. It doesn’t use division.

Note

If no solution exists, and random is true, this method will never finish.

class vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem(A, B, b, c, result=None)

A class for inhomogeneous linear inequality systems

A x <= b, B x <= c

exists_orthogonal_vector(v) → bool

Check if an orthogonal vector exists in the intervals.

get_intervals() → list

Return the corresponding intervals.

to_homogeneous()

Return the equivalent homogeneous system.

class vectors_in_intervals.linear_inequality_systems.LinearInequalitySystem(_matrix, intervals, result=None)

A class for linear inequality systems given by a matrix and intervals

candidate_generator(kernel: bool = True, reverse: bool = False, random: bool = False) → collections.abc.Generator

Return a generator of elementary vectors.

certify(reverse: bool = False) → tuple

Return a boolean and a certificate for solvability.

certify_existence(reverse: bool = False, random: bool = False)

Certify existence of a solution if one exists.

Otherwise, a ValueError is raised.

Note

If a solution exists and random is set to true, this method will never finish.

certify_nonexistence(reverse: bool = False, random: bool = False)

Certify nonexistence of solutions.

Otherwise, a ValueError is raised.

Note

If a solution exists and random is set to true, this method will never finish.

certify_parallel(reverse: bool = False, random: bool = False) → tuple

Return a boolean and a certificate for solvability.

Attempts to find a solution and certify nonexistence in parallel.

exists_orthogonal_vector(v) → bool

Check if an orthogonal vector exists in the intervals.

get_intervals() → list

Return the corresponding intervals.

solve(reverse: bool = False, random: bool = False)

Compute a solution for this linear inequality system.

If no solution exists, a ValueError is raised.

to_homogeneous()

Return the equivalent homogeneous system.

vectors_in_intervals.linear_inequality_systems.homogeneous_from_general(system: vectors_in_intervals.linear_inequality_systems.LinearInequalitySystem) → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem

Convert a general system to a homogeneous system.

EXAMPLE:

sage: from vectors_in_intervals import *
sage: M = matrix([[1, 0], [0, 1], [1, 1]])
sage: lower_bounds = [2, 5, 0]
sage: upper_bounds = [5, oo, 0]
sage: lower_bounds_closed = [True, True, True]
sage: upper_bounds_closed = [False, False, True]
sage: I = intervals_from_bounds(lower_bounds, upper_bounds, lower_bounds_closed, upper_bounds_closed)
sage: S = LinearInequalitySystem(M, I)
sage: homogeneous_from_general(S)
[ 1  0 -5]
[ 0  0 -1]
[--------]
[-1  0  2]
[ 0 -1  5]
[--------]
[ 1  1  0] x in [(0, +oo), (0, +oo), [0, +oo), [0, +oo), {0}]

vectors_in_intervals.linear_inequality_systems.homogeneous_from_inhomogeneous(system: vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem) → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem

Convert an inhomogeneous system to a homogeneous system.

vectors_in_intervals.linear_inequality_systems.inhomogeneous_from_general(system: vectors_in_intervals.linear_inequality_systems.LinearInequalitySystem) → vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem

Translate a general system into an inhomogeneous system.