Annotation of OpenXM_contrib/PHC/Ada/Math_Lib/Matrices/generic_integer_linear_solvers.ads, Revision 1.1
1.1 ! maekawa 1: with Standard_Integer_Vectors;
! 2: with Abstract_Ring,Abstract_Ring.Domain;
! 3: with Generic_Vectors,Generic_Matrices;
! 4: with Greatest_Common_Divisors;
! 5:
! 6: generic
! 7:
! 8: with package Ring is new Abstract_Ring(<>);
! 9: with package Domain is new Ring.Domain(<>);
! 10: with package Vectors is new Generic_Vectors(Ring);
! 11: with package Matrices is new Generic_Matrices(Ring,Vectors);
! 12: with package Common_Divisors is new Greatest_Common_Divisors(Ring,Domain);
! 13:
! 14: package Generic_Integer_Linear_Solvers is
! 15:
! 16: -- DESCRIPTION :
! 17: -- This package offers a routines for solving linear systems over a domain.
! 18:
! 19: use Ring,Domain,Matrices;
! 20:
! 21: -- SCALERS :
! 22:
! 23: function Scale ( a : Matrix ) return Matrix;
! 24: procedure Scale ( a : in out Matrix; v : out Vectors.Vector );
! 25: procedure Scale ( a : in out Matrix );
! 26:
! 27: -- DESCRIPTION :
! 28: -- Every row of the matrix will be divided by the greatest commom divisor
! 29: -- of the elements on that row. The divisors are returned in the vector v
! 30: -- if the appropiate call has been made.
! 31:
! 32: procedure Scale ( a : in out Matrix; row,col : in integer );
! 33:
! 34: -- DESCRIPTION :
! 35: -- Scales a(row,col..a'last(2)).
! 36:
! 37: -- STATIC TRIANGULATORS :
! 38:
! 39: procedure Upper_Triangulate ( l : out Matrix; a : in out Matrix );
! 40: procedure Upper_Triangulate ( a : in out Matrix );
! 41:
! 42: -- DESCRIPTION :
! 43: -- a := l*a, l makes a upper triangular,
! 44: -- l*a becomes then the Hermite normal form of a.
! 45:
! 46: -- ON ENTRY :
! 47: -- a an integer matrix.
! 48:
! 49: -- ON RETURN :
! 50: -- l the transformation matrix;
! 51: -- a the triangulated matrix.
! 52:
! 53: procedure Lower_Triangulate ( a : in out Matrix; u : out Matrix );
! 54: procedure Lower_Triangulate ( a : in out Matrix );
! 55:
! 56: -- DESCRIPTION :
! 57: -- a := a*u, u makes a lower triangular.
! 58:
! 59: -- ON ENTRY :
! 60: -- a an integer matrix.
! 61:
! 62: -- ON RETURN :
! 63: -- a the triangulated matrix;
! 64: -- u the transformation matrix.
! 65:
! 66: -- DYNAMIC TRIANGULATOR :
! 67:
! 68: procedure Triangulate ( l : in integer; m : in out matrix;
! 69: ipvt : in out Standard_Integer_Vectors.Vector;
! 70: piv : out integer );
! 71:
! 72: -- DESCRIPTION :
! 73: -- Updates lth row of m such that m remains upper triangular.
! 74: -- Note that the last column of m will never be involved in
! 75: -- pivoting operations. In this way, one can regard the last
! 76: -- column of m as the right hand side of the system a*x = b,
! 77: -- with m = [a|-b].
! 78:
! 79: -- REQUIRED : l in m'range(1) and m'range(2) = ipvt'range.
! 80:
! 81: -- ON ENTRY :
! 82: -- l indicates which row in m that has to be updated;
! 83: -- m first l-1 rows are upper triangular;
! 84: -- ipvt contains the pivoting information;
! 85:
! 86: -- ON RETURN :
! 87: -- m m(1..l,m'range(2)) is upper triangular;
! 88: -- ipvt updated pivoting information;
! 89: -- piv first entry on lth row of m that was nonzero,
! 90: -- if piv /= l then two columns have been interchanged.
! 91: -- if piv = 0, then m(l,i) = 0, for i < m'last(2).
! 92:
! 93: procedure Switch ( ipvt : in Standard_Integer_Vectors.Vector;
! 94: first,last : in integer; m : in out matrix);
! 95: procedure Switch ( ipvt : in Standard_Integer_Vectors.Vector;
! 96: index : in integer; m : in out matrix );
! 97:
! 98: procedure Switch ( l,pivot,index : in integer; m : in out matrix );
! 99: procedure Switch ( l,pivot : in integer;
! 100: first,last : in integer; m : in out matrix );
! 101:
! 102: -- DESCRIPTION :
! 103: -- Performs column interchangements on m(first..last) or m(index),
! 104: -- with the pivoting information generated by Triangulate,
! 105: -- w.r.t. the lth unknown and pivot, or w.r.t. the pivoting vector ipvt.
! 106:
! 107: -- SELECTORS :
! 108:
! 109: function Det ( a : Matrix ) return number;
! 110:
! 111: -- DESCRIPTION :
! 112: -- First the matrix a will be triangulated and then
! 113: -- the determinant of the matrix a will be returned.
! 114:
! 115: function Per ( a : Matrix; k : Standard_Integer_Vectors.Vector )
! 116: return number;
! 117: function Per ( a : Matrix; k : Standard_Integer_Vectors.Vector;
! 118: max : number ) return number;
! 119:
! 120: -- DESCRIPTION : Returns the permanent of a matrix.
! 121:
! 122: -- ON ENTRY
! 123: -- a (n*m)-matrix, with m <= n;
! 124: -- k vector(1..m), k(i) indicates the multiplicity
! 125: -- of the ith column;
! 126: -- max the computation stops when the result >= max.
! 127:
! 128: function Rank ( a : Matrix ) return natural;
! 129:
! 130: -- DESCRIPTION :
! 131: -- returns the rank of the matrix a.
! 132:
! 133: -- SOLVERS :
! 134:
! 135: procedure Solve0 ( a : in Matrix; x : in out Vectors.Vector );
! 136:
! 137: -- DESCRIPTION :
! 138: -- computes a solution of a*x = 0; where a is upper triangular.
! 139: -- If the number of linear independent rows in a is less than
! 140: -- the number of colums in a, then x will have a nonzero component.
! 141:
! 142: -- REQUIRED :
! 143: -- a'range(2) = x'range;
! 144: -- Scale(a) should be applied before calling this procedure.
! 145:
! 146: procedure Solve1 ( a : in Matrix; x : in out Vectors.Vector;
! 147: b : in Vectors.Vector; fail : out boolean );
! 148:
! 149: -- DESCRIPTION :
! 150: -- computes the solution of a*x = b, where a is upper triangular.
! 151: -- If Det(a)*Det(a) /= 1, then an integer solutions cannot be
! 152: -- guaranteed, so fail can become true.
! 153:
! 154: -- REQUIRED :
! 155: -- The matrix a must be square and all ranges must match.
! 156:
! 157: procedure Solve1 ( a : in Matrix; b : in out Vectors.Vector;
! 158: fail : out boolean );
! 159:
! 160: -- DESCRIPTION :
! 161: -- computes the solution of a*x = b, where a is upper triangular,
! 162: -- but after computation, the vector x is stored in b.
! 163: -- If Det(a)*Det(a) /= 1, then an integer solution cannot be
! 164: -- guaranteed, so fail can become true.
! 165:
! 166: -- REQUIRED :
! 167: -- The matrix a must be square and all ranges must be the same.
! 168:
! 169: function Solve ( m : matrix; ipvt : Standard_Integer_Vectors.Vector )
! 170: return Vectors.Vector;
! 171:
! 172: -- DESCRIPTION :
! 173: -- Solves the system defined by m*x = 0, with m an upper triangular
! 174: -- matrix. The vector ipvt contains the pivoting information:
! 175: -- ipvt(k) = position of kth column.
! 176:
! 177: -- REQUIRED : m'range(2) = m'range(1).
! 178:
! 179: -- ON RETURN : solution vector with nonnegative last component.
! 180:
! 181: end Generic_Integer_Linear_Solvers;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>