A generic class for solvers of linear systems

Python file for an implementation of linear solver.

This module offers an abstract class that represents a solver for a linear system. This class stablish a common interface for all the linear solvers that can be used.

This module also includes one toy implementation that uses Sage solving methods to compute the solutions to a linear system with coefficients in integral domains (since we build the field of fractions).

AUTHORS:

• Antonio Jimenez-Pastor (2021-02-09): initial version

class ajpastor.misc.linear_solver.LinearSystemSolver(parent, matrix, inhomogeneous, is_zero=<function LinearSystemSolver.<lambda> at 0x7f19318fd1f0>, relations=[])

Bases: object

Generic class for solving a linear system.

The methods described in this class are an interface that all the subclasses must implement. This allow the user to change between algorithms very easily since all the information that can be extracted has always the same format.

A linear system is always given in the form

\[A \alpha = \mathbf{b},\]

where \(A\) is a matrix of size \(n\times m\) with coefficients in a ring \(R\), \(\mathbf{b}\) is the inhomogeneous term, i.e., a column vector of size \(n\) also with entries in the ring \(R\)) and \(\alpha\) a column vector of size \(m\) that represents the unknowns of the system.

A

Alias for system_matrix()

H

Alias for echelon_form()

U

Alias for transformation_matrix()

b

Alias for inhomogeneous()

echelon_form()

Method that returns the echelon form of the system matrix.

This method returns the echelon form computed by the current algorithm in order to solve the linear system. The structure of this matrix is highly dependent on the algorithm and it can be upper-triangular, lower-triangular, diagonal, etc.

have_ideal()

Auxiliary method to know if some relation have been already found.

This method returns True if the current Groebner basis we have computed gives some non-trivial ideal.

inhomogeneous()

Method that returns the inhomogeneous vector of the linear system.

This method returns the original inhomogeneous vector provided to present the linear system.

is_homogeneous()

Method that return whether the system is homogeneous or not.

This method checks if all the elements in the vector \(\mathbf{b}\) are zero. This checking may lead to more relations on the system considered and will be added, as expected, in the relation ideal that the algorithm have.

is_zero(el)

Method to check whether an element is the zero element or not.

This method computes the real value of el and checks if it is zero or not regardless of its representation. In case the elements was not trivial, we add it to the ideal of relations and update the Gröbner basis.

parent()

Method that returns the ring \(R\) where the system is defined.

The matrix \(A\) and the vector \(\mathbf{b}\) have their coefficients in a common ring (or at least in rings where Sage can compute the pushout). This method returns such ring. This ring may be different from the ring where we look for solutions to the system \(A\alpha = \mathbf{b}\), but it will always be included in it.

In order to know the ring where the solutions are searched, see the method solution_parent().

rank()

Method that returns the rank of the system matrix.

This methods returns the rank of the system matrix. This rank is the maximal number of rows of the system that are linearly independent. This number usually defines the dimension of the solution space of the system.

relations()

Method to get the current known relations in the ring.

simplify(obj)

Method to simplify an object using the relations found.

This method simplifies an object (either an element, vector, list, tuple or matrix) using the relations that we found during the computation of the solutions of this linear system.

WARNING: repeated executions of this method may return different outputs since we may have found more relations.

solution()

Method that returns a particular solution to the linear system.

This method computes a particular vector \(\alpha\) that solves the linear system \(A\alpha = \mathbf{b}\) in the parent given by LinearSystemSolver.solution_parent().

solution_parent()

Method that returns the ring where the solutions to the system are searched.

The matrix \(A\) and the vector \(\mathbf{b}\) have their coefficients in a common ring (or at least in rings where Sage can compute the pushout). This ring may be different from the ring where we look for solutions to the system \(A\alpha = \mathbf{b}\), but it will always be included in it. This method returns that ring where we look for solutions.

In order to know the ring of the matrix \(A\) and vector \(\mathbf{b}\), see the method parent().

system_matrix()

Method that returns the matrix of the linear system.

This method returns the original matrix provided to present the linear system.

syzygy()

Method that returns the solution space for the homogeneous system.

Given a linear system \(A\alpha = \mathbf{b}\), it is clear that for any two solutions \(\alpha_1,\alpha_2\) we have that its difference is a solution to the homogeneous linear system \(A\beta = \mathbf{0}\).

This method computes the solution space of the homogeneous system and return it as a matrix \(S\) of size \(m\times p\) where \(m\) is the number of columns of \(A\) and \(p\) the dimension of the solution space. Hence, any solution to the original system can be written as

\[\alpha_0 + S\beta\]

where \(\alpha_0\) is a particular solution to the linear system \(A\alpha_0 = \mathbf{b}\) and \(\beta\) is any vector with entries in the parent for the solutions.

transformation_matrix()

Method that returns the transformation matrix of the system

This method returns a square matrix \(U\) that transforms the linear system matrix into the echelon form. This means that if \(H\) is the echelon form of the system matrix \(A\), then

\[UA = H\]

This matrix is computed simultaneously to the echelon form of the system.

exception ajpastor.misc.linear_solver.NoSolutionError

Bases: ValueError

class ajpastor.misc.linear_solver.SageSolver(parent, matrix, inhomogeneous)

Bases: ajpastor.misc.linear_solver.LinearSystemSolver

Toy implementation of a LinearSystemSolver.

This class is a simple example on how to implement specific classes for LinearSystemSolver. This class uses Sage method to compute the solutions, the echelon form, etc.

WARNING (trac ticket #23715): sometimes, the method echelon_form ignore the transformation argument, so the output is None.