Annotation of OpenXM_contrib/PHC/Ada/Math_Lib/Matrices/generic_integer_linear_solvers.ads, Revision 1.1.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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to generic_integer_linear_solvers.ads CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / PHC / Ada / Math_Lib / Matrices