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.intervals
(0, +oo) x (0, +oo) x [0, +oo) x {0}
sage: S.find_solution()
(0, 1)
sage: S.certify()
(True, (0, 1))
sage: S.certify(random=True)
(True, (0, 1))

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.find_solution()
(5/2, 5)
sage: S.certify()
(True, (5/2, 5))

sage: S.to_inhomogeneous()
[ 1  0]
[-1 -1]
[ 1  1]
[-----]
[-1  0]
[ 0 -1]
[ 0  1] x in (-oo, 5) x (-oo, 0) x (-oo, 8) x (-oo, -2] x (-oo, -5] x (-oo, 5]
sage: S.to_homogeneous()
[ 1  0 -5]
[-1 -1  0]
[ 1  1 -8]
[ 0  0 -1]
[--------]
[-1  0  2]
[ 0 -1  5]
[ 0  1 -5]
[--------] x in (0, +oo) x (0, +oo) x (0, +oo) x (0, +oo) x [0, +oo) x [0, +oo) x [0, +oo)

We consider yet another system:

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

sage: S.to_homogeneous()
[-1 -1  0]
[ 0  0 -1]
[--------]
[ 1  0 -1]
[ 1  1  0]
[--------] x in (0, +oo) x (0, +oo) x [0, +oo) x [0, +oo)

TESTS:

sage: A = matrix([[1, 1]])
sage: B = matrix([[0, 1]])
sage: C = matrix([[1, -1]])
sage: S = HomogeneousSystem(A, B, C)
sage: S
[ 1  1]
[-----]
[ 0  1]
[-----]
[ 1 -1] x in (0, +oo) x [0, +oo) x {0}
sage: S.to_inhomogeneous()
[-1 -1]
[-----]
[ 0 -1]
[-1  1]
[ 1 -1] x in (-oo, 0) x (-oo, 0] x (-oo, 0] x (-oo, 0]
sage: S.to_inhomogeneous().to_homogeneous()
[-1 -1  0]
[ 0  0 -1]
[--------]
[ 0 -1  0]
[-1  1  0]
[ 1 -1  0]
[--------] x in (0, +oo) x (0, +oo) x [0, +oo) x [0, +oo) x [0, +oo)
sage: S.to_inhomogeneous().to_homogeneous().to_inhomogeneous()
[ 1  1  0]
[ 0  0  1]
[--------]
[ 0  1  0]
[ 1 -1  0]
[-1  1  0] x in (-oo, 0) x (-oo, 0) x (-oo, 0] x (-oo, 0] x (-oo, 0]

Classes

`HomogeneousSystem`(matrix_strict, ...)	A class for homogeneous linear inequality systems.
`InhomogeneousSystem`(matrix_strict, ...)	A class for inhomogeneous linear inequality systems.
`LinearInequalitySystem`(matrix[, intervals])	A class for linear inequality systems given by a matrix and intervals.

Exceptions

`MaxIterationsReachedError`	Raised when the maximum number of iterations is reached.
`ProcessStoppedError`	Raised when the process was stopped by another process.

class vectors_in_intervals.linear_inequality_systems.HomogeneousSystem(matrix_strict: sage.matrix.constructor.matrix, matrix_nonstrict: sage.matrix.constructor.matrix, matrix_zero: sage.matrix.constructor.matrix)¶

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()
(True, (-1, 1))

category(self)¶: File: sage/structure/sage_object.pyx (starting at line 484)

certify(random: bool = False, iteration_limit: int = - 1) → tuple[bool, sage.modules.free_module_element.vector]¶

Return a boolean and a certificate for solvability.

Both existence and nonexistence are checked in parallel.

INPUT:

random – if true, elementary vectors are generated randomly
iteration_limit – maximum number of iterations for each process (by default unlimited)

OUTPUT: A tuple (exists, certificate) where exists is a boolean indicating whether a solution exists, and certificate is either a solution (if exists is true) or a vector certifying nonexistence (if exists is false).

certify_nonexistence(random: bool = False, iteration_limit: int = 10000) → sage.modules.free_module_element.vector¶

Certify nonexistence of a solution if no solution exists.

INPUT:

random – if true, tries random elementary vectors
iteration_limit – maximum number of iterations (by default 10000). If -1, unlimited.

OUTPUT: A vector certifying that no solution exists.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If a solution exists, a ValueError is raised.
If a solution exists, the iteration limit is -1 _and_ random is true, this leads to an endless loop.

dual() → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem¶: Return the dual linear inequality system.

dump(self, filename, compress=True)¶

File: sage/structure/sage_object.pyx (starting at line 445)

Same as self.save(filename, compress)

dumps(self, compress=True)¶

File: sage/structure/sage_object.pyx (starting at line 451)

Dump self to a string s, which can later be reconstituted as self using loads(s).

There is an optional boolean argument compress which defaults to True.

EXAMPLES:

sage: from sage.misc.persist import comp
sage: O = SageObject()
sage: p_comp = O.dumps()
sage: p_uncomp = O.dumps(compress=False)
sage: comp.decompress(p_comp) == p_uncomp
True
sage: import pickletools
sage: pickletools.dis(p_uncomp)
    0: \x80 PROTO      2
    2: c    GLOBAL     'sage.structure.sage_object SageObject'
   41: q    BINPUT     ...
   43: )    EMPTY_TUPLE
   44: \x81 NEWOBJ
   45: q    BINPUT     ...
   47: .    STOP
highest protocol among opcodes = 2

find_solution(random: bool = False, iteration_limit: int = 10000) → sage.modules.free_module_element.vector¶

Compute a solution if existent.

INPUT:

random – if true, the returned sum consists of random elementary vectors
iteration_limit – maximum number of iterations (by default 10000). If -1, unlimited.

OUTPUT: A vector (as a sum of elementary vectors) solving the system.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If no solution exists, a ValueError is raised.
If no solution exists, the iteration limit is -1 _and_ random is true, this leads to an endless loop.

See also

certify()

property intervals: vectors_in_intervals.intervals.Intervals¶: Return the corresponding intervals.

property matrix: sage.matrix.constructor.matrix¶: Return the corresponding matrix.

parent(self)¶

File: sage/structure/sage_object.pyx (starting at line 518)

Return the type of self to support the coercion framework.

EXAMPLES:

sage: t = log(sqrt(2) - 1) + log(sqrt(2) + 1); t
log(sqrt(2) + 1) + log(sqrt(2) - 1)
sage: u = t.maxima_methods()
sage: u.parent()
<class 'sage.symbolic.maxima_wrapper.MaximaWrapper'>

rename(self, x=None)¶

File: sage/structure/sage_object.pyx (starting at line 68)

Change self so it prints as x, where x is a string.

Note

This is only supported for Python classes that derive from SageObject.

EXAMPLES:

sage: x = PolynomialRing(QQ, 'x', sparse=True).gen()
sage: g = x^3 + x - 5
sage: g
x^3 + x - 5
sage: g.rename('a polynomial')
sage: g
a polynomial
sage: g + x
x^3 + 2*x - 5
sage: h = g^100
sage: str(h)[:20]
'x^300 + 100*x^298 - '
sage: h.rename('x^300 + ...')
sage: h
x^300 + ...

Real numbers are not Python classes, so rename is not supported:

sage: a = 3.14
sage: type(a)
<... 'sage.rings.real_mpfr.RealLiteral'>
sage: a.rename('pi')
Traceback (most recent call last):
...
NotImplementedError: object does not support renaming: 3.14000000000000

Note

The reason C-extension types are not supported by default is if they were then every single one would have to carry around an extra attribute, which would be slower and waste a lot of memory.

To support them for a specific class, add a cdef public __custom_name attribute.

reset_name(self)¶

File: sage/structure/sage_object.pyx (starting at line 125)

Remove the custom name of an object.

EXAMPLES:

sage: P.<x> = QQ[]
sage: P
Univariate Polynomial Ring in x over Rational Field
sage: P.rename('A polynomial ring')
sage: P
A polynomial ring
sage: P.reset_name()
sage: P
Univariate Polynomial Ring in x over Rational Field

save(self, filename=None, compress=True)¶

File: sage/structure/sage_object.pyx (starting at line 420)

Save self to the given filename.

EXAMPLES:

sage: f = x^3 + 5
sage: f.save(os.path.join(SAGE_TMP, 'file'))
sage: load(os.path.join(SAGE_TMP, 'file.sobj'))
x^3 + 5

to_homogeneous() → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem¶: Return the equivalent homogeneous system.

to_inhomogeneous() → vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem¶: Return the equivalent inhomogeneous system.

with_intervals(intervals: vectors_in_intervals.intervals.Intervals) → vectors_in_intervals.linear_inequality_systems.LinearInequalitySystem¶

Return a copy of this system with different intervals.

TESTS:

sage: from vectors_in_intervals import *
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.certify()
(True, (5/2, 5))
sage: S.with_intervals(I).certify()
(True, (5/2, 5))
sage: S.with_intervals(Intervals.from_bounds([2, 6, 0, -oo], [5, oo, 8, 5])).certify()
(False, (0, 1, 0, -1))
sage: S.with_intervals(Intervals.from_bounds([2, 5, 0, -oo], [5, 5, 8, 5])).certify()
(True, (2, 5))

class vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem(matrix_strict: sage.matrix.constructor.matrix, matrix_nonstrict: sage.matrix.constructor.matrix, vector_strict: sage.modules.free_module_element.vector, vector_nonstrict: sage.modules.free_module_element.vector)¶

A class for inhomogeneous linear inequality systems.

A x < a, B x <= b

category(self)¶: File: sage/structure/sage_object.pyx (starting at line 484)

certify(random: bool = False, iteration_limit: int = - 1) → tuple[bool, sage.modules.free_module_element.vector]¶

Return a boolean and a certificate for solvability.

Both existence and nonexistence are checked in parallel.

INPUT:

random – if true, elementary vectors are generated randomly
iteration_limit – maximum number of iterations for each process (by default unlimited)

OUTPUT: A tuple (exists, certificate) where exists is a boolean indicating whether a solution exists, and certificate is either a solution (if exists is true) or a vector certifying nonexistence (if exists is false).

certify_nonexistence(random: bool = False, iteration_limit: int = 10000) → sage.modules.free_module_element.vector¶

Certify nonexistence of a solution if no solution exists.

INPUT:

random – if true, tries random elementary vectors
iteration_limit – maximum number of iterations (by default 10000). If -1, unlimited.

OUTPUT: A vector certifying that no solution exists.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If a solution exists, a ValueError is raised.
If a solution exists, the iteration limit is -1 _and_ random is true, this leads to an endless loop.

dual() → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem¶: Return the dual linear inequality system.

dump(self, filename, compress=True)¶

File: sage/structure/sage_object.pyx (starting at line 445)

Same as self.save(filename, compress)

dumps(self, compress=True)¶

File: sage/structure/sage_object.pyx (starting at line 451)

Dump self to a string s, which can later be reconstituted as self using loads(s).

There is an optional boolean argument compress which defaults to True.

EXAMPLES:

sage: from sage.misc.persist import comp
sage: O = SageObject()
sage: p_comp = O.dumps()
sage: p_uncomp = O.dumps(compress=False)
sage: comp.decompress(p_comp) == p_uncomp
True
sage: import pickletools
sage: pickletools.dis(p_uncomp)
    0: \x80 PROTO      2
    2: c    GLOBAL     'sage.structure.sage_object SageObject'
   41: q    BINPUT     ...
   43: )    EMPTY_TUPLE
   44: \x81 NEWOBJ
   45: q    BINPUT     ...
   47: .    STOP
highest protocol among opcodes = 2

find_solution(random: bool = False, iteration_limit: int = 10000) → sage.modules.free_module_element.vector¶

Compute a solution if existent.

INPUT:

random – if true, the returned sum consists of random elementary vectors
iteration_limit – maximum number of iterations (by default 10000). If -1, unlimited.

OUTPUT: A vector (as a sum of elementary vectors) solving the system.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If no solution exists, a ValueError is raised.
If no solution exists, the iteration limit is -1 _and_ random is true, this leads to an endless loop.

See also

certify()

property intervals: vectors_in_intervals.intervals.Intervals¶: Return the corresponding intervals.

property matrix: sage.matrix.constructor.matrix¶: Return the corresponding matrix.

parent(self)¶

File: sage/structure/sage_object.pyx (starting at line 518)

Return the type of self to support the coercion framework.

EXAMPLES:

sage: t = log(sqrt(2) - 1) + log(sqrt(2) + 1); t
log(sqrt(2) + 1) + log(sqrt(2) - 1)
sage: u = t.maxima_methods()
sage: u.parent()
<class 'sage.symbolic.maxima_wrapper.MaximaWrapper'>

rename(self, x=None)¶

File: sage/structure/sage_object.pyx (starting at line 68)

Change self so it prints as x, where x is a string.

Note

This is only supported for Python classes that derive from SageObject.

EXAMPLES:

sage: x = PolynomialRing(QQ, 'x', sparse=True).gen()
sage: g = x^3 + x - 5
sage: g
x^3 + x - 5
sage: g.rename('a polynomial')
sage: g
a polynomial
sage: g + x
x^3 + 2*x - 5
sage: h = g^100
sage: str(h)[:20]
'x^300 + 100*x^298 - '
sage: h.rename('x^300 + ...')
sage: h
x^300 + ...

Real numbers are not Python classes, so rename is not supported:

sage: a = 3.14
sage: type(a)
<... 'sage.rings.real_mpfr.RealLiteral'>
sage: a.rename('pi')
Traceback (most recent call last):
...
NotImplementedError: object does not support renaming: 3.14000000000000

Note

The reason C-extension types are not supported by default is if they were then every single one would have to carry around an extra attribute, which would be slower and waste a lot of memory.

To support them for a specific class, add a cdef public __custom_name attribute.

reset_name(self)¶

File: sage/structure/sage_object.pyx (starting at line 125)

Remove the custom name of an object.

EXAMPLES:

sage: P.<x> = QQ[]
sage: P
Univariate Polynomial Ring in x over Rational Field
sage: P.rename('A polynomial ring')
sage: P
A polynomial ring
sage: P.reset_name()
sage: P
Univariate Polynomial Ring in x over Rational Field

save(self, filename=None, compress=True)¶

File: sage/structure/sage_object.pyx (starting at line 420)

Save self to the given filename.

EXAMPLES:

sage: f = x^3 + 5
sage: f.save(os.path.join(SAGE_TMP, 'file'))
sage: load(os.path.join(SAGE_TMP, 'file.sobj'))
x^3 + 5

to_homogeneous() → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem¶: Return the equivalent homogeneous system.

to_inhomogeneous() → vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem¶: Return the equivalent inhomogeneous system.

with_intervals(intervals: vectors_in_intervals.intervals.Intervals) → vectors_in_intervals.linear_inequality_systems.LinearInequalitySystem¶

Return a copy of this system with different intervals.

TESTS:

sage: from vectors_in_intervals import *
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.certify()
(True, (5/2, 5))
sage: S.with_intervals(I).certify()
(True, (5/2, 5))
sage: S.with_intervals(Intervals.from_bounds([2, 6, 0, -oo], [5, oo, 8, 5])).certify()
(False, (0, 1, 0, -1))
sage: S.with_intervals(Intervals.from_bounds([2, 5, 0, -oo], [5, 5, 8, 5])).certify()
(True, (2, 5))

class vectors_in_intervals.linear_inequality_systems.LinearInequalitySystem(matrix: sage.matrix.constructor.matrix, intervals: Optional[vectors_in_intervals.intervals.Intervals] = None)¶

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

category(self)¶: File: sage/structure/sage_object.pyx (starting at line 484)

certify(random: bool = False, iteration_limit: int = - 1) → tuple[bool, sage.modules.free_module_element.vector]¶

Return a boolean and a certificate for solvability.

Both existence and nonexistence are checked in parallel.

INPUT:

random – if true, elementary vectors are generated randomly
iteration_limit – maximum number of iterations for each process (by default unlimited)

OUTPUT: A tuple (exists, certificate) where exists is a boolean indicating whether a solution exists, and certificate is either a solution (if exists is true) or a vector certifying nonexistence (if exists is false).

certify_nonexistence(random: bool = False, iteration_limit: int = 10000) → sage.modules.free_module_element.vector¶

Certify nonexistence of a solution if no solution exists.

INPUT:

random – if true, tries random elementary vectors
iteration_limit – maximum number of iterations (by default 10000). If -1, unlimited.

OUTPUT: A vector certifying that no solution exists.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If a solution exists, a ValueError is raised.
If a solution exists, the iteration limit is -1 _and_ random is true, this leads to an endless loop.

dual() → vectors_in_intervals.linear_inequality_systems.LinearInequalitySystem¶: Return the dual linear inequality system.

dump(self, filename, compress=True)¶

File: sage/structure/sage_object.pyx (starting at line 445)

Same as self.save(filename, compress)

dumps(self, compress=True)¶

File: sage/structure/sage_object.pyx (starting at line 451)

Dump self to a string s, which can later be reconstituted as self using loads(s).

There is an optional boolean argument compress which defaults to True.

EXAMPLES:

sage: from sage.misc.persist import comp
sage: O = SageObject()
sage: p_comp = O.dumps()
sage: p_uncomp = O.dumps(compress=False)
sage: comp.decompress(p_comp) == p_uncomp
True
sage: import pickletools
sage: pickletools.dis(p_uncomp)
    0: \x80 PROTO      2
    2: c    GLOBAL     'sage.structure.sage_object SageObject'
   41: q    BINPUT     ...
   43: )    EMPTY_TUPLE
   44: \x81 NEWOBJ
   45: q    BINPUT     ...
   47: .    STOP
highest protocol among opcodes = 2

find_solution(random: bool = False, iteration_limit: int = 10000) → sage.modules.free_module_element.vector¶

Compute a solution if existent.

INPUT:

random – if true, the returned sum consists of random elementary vectors
iteration_limit – maximum number of iterations (by default 10000). If -1, unlimited.

OUTPUT: A vector (as a sum of elementary vectors) solving the system.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If no solution exists, a ValueError is raised.
If no solution exists, the iteration limit is -1 _and_ random is true, this leads to an endless loop.

vectors_in_intervals.linear_inequality_systems¶

Linear inequality systems¶

Table of Contents

Previous topic

Next topic

This Page