Return to generic_integer_linear_solvers.ads CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Math_Lib / Matrices

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;