libroutines

IML package provides efficient routines to solve nonsingular systems of linear equations, certifie

This file explains the functions of the library routines. 

Note:
  Type FiniteField is defined as unsigned long
  Type Double is defined as double


extern void nonsingSolvMM (const enum SOLU_POS solupos, const long n, 
                           const long m, const long *A, mpz_t *mp_B, 
			   mpz_t *mp_N, mpz_t mp_D);

/*
 * Calling Sequence:
 *   nonsingSolvMM(solupos, n, m, A, mp_B, mp_N, mp_D)
 *
 * Summary:
 *   Solve nonsingular system of linear equations, where the left hand side 
 *   input matrix is a signed long matrix.
 *
 * Description:
 *   Given a n x n nonsingular signed long matrix A, a n x m or m x n mpz_t 
 *   matrix mp_B, this function will compute the solution of the system
 *   1. AX = mp_B 
 *   2. XA = mp_B. 
 *   The parameter solupos controls whether the system is in the type of 1
 *   or 2.
 *   
 *   Since the unique solution X is a rational matrix, the function will
 *   output the numerator matrix mp_N and denominator mp_D respectively, 
 *   such that A(mp_N) = mp_D*mp_B or (mp_N)A = mp_D*mp_B. 
 *
 * Input: 
 *   solupos: enumerate, flag to indicate the system to be solved
 *          - solupos = LeftSolu: solve XA = mp_B
 *          - solupos = RightSolu: solve AX = mp_B
 *         n: long, dimension of A
 *         m: long, column or row dimension of mp_B depending on solupos
 *         A: 1-dim signed long array length n*n, representing the n x n
 *            left hand side input matrix
 *      mp_B: 1-dim mpz_t array length n*m, representing the right hand side
 *            matrix of the system
 *          - solupos = LeftSolu: mp_B a m x n matrix
 *          - solupos = RightSolu: mp_B a n x m matrix
 * 
 * Output:
 *   mp_N: 1-dim mpz_t array length n*m, representing the numerator matrix 
 *         of the solution
 *       - solupos = LeftSolu: mp_N a m x n matrix
 *       - solupos = RightSolu: mp_N a n x m matrix
 *   mp_D: mpz_t, denominator of the solution
 *
 * Precondition: 
 *   A must be a nonsingular matrix.
 *
 * Note:
 *   - It is necessary to make sure the input parameters are correct,
 *     expecially the dimension, since there is no parameter checks in the 
 *     function.
 *   - Input and output matrices are row majored and represented by
 *     one-dimension array.
 *   - It is needed to preallocate the memory space of mp_N and mp_D. 
 *
 */



extern void nonsingSolvLlhsMM (const enum SOLU_POS solupos, const long n, 
			       const long m, mpz_t *mp_A, mpz_t *mp_B, 
			       mpz_t *mp_N, mpz_t mp_D);

/*
 * Calling Sequence:
 *   nonsingSolvLlhsMM(solupos, n, m, mp_A, mp_B, mp_N, mp_D)
 *
 * Summary:
 *   Solve nonsingular system of linear equations, where the left hand side 
 *   input matrix is a mpz_t matrix.
 *
 * Description:
 *   Given a n x n nonsingular mpz_t matrix A, a n x m or m x n mpz_t 
 *   matrix mp_B, this function will compute the solution of the system
 *   1. (mp_A)X = mp_B 
 *   2. X(mp_A) = mp_B. 
 *   The parameter solupos controls whether the system is in the type of 1
 *   or 2.
 *   
 *   Since the unique solution X is a rational matrix, the function will
 *   output the numerator matrix mp_N and denominator mp_D respectively, 
 *   such that mp_Amp_N = mp_D*mp_B or mp_Nmp_A = mp_D*mp_B. 
 *
 * Input:
 *   solupos: enumerate, flag to indicate the system to be solved
 *          - solupos = LeftSolu: solve XA = mp_B
 *          - solupos = RightSolu: solve AX = mp_B
 *         n: long, dimension of A
 *         m: long, column or row dimension of mp_B depending on solupos
 *      mp_A: 1-dim mpz_t array length n*n, representing the n x n left hand
 *            side input matrix
 *      mp_B: 1-dim mpz_t array length n*m, representing the right hand side
 *            matrix of the system
 *          - solupos = LeftSolu: mp_B a m x n matrix
 *          - solupos = RightSolu: mp_B a n x m matrix
 * 
 * Output:
 *   mp_N: 1-dim mpz_t array length n*m, representing the numerator matrix 
 *         of the solution
 *       - solupos = LeftSolu: mp_N a m x n matrix
 *       - solupos = RightSolu: mp_N a n x m matrix
 *   mp_D: mpz_t, denominator of the solution
 *
 * Precondition: 
 *   mp_A must be a nonsingular matrix.
 *
 * Note:
 *   - It is necessary to make sure the input parameters are correct,
 *     expecially the dimension, since there is no parameter checks in the 
 *     function.
 *   - Input and output matrices are row majored and represented by
 *     one-dimension array.
 *   - It is needed to preallocate the memory space of mp_N and mp_D. 
 *
 */



extern void nonsingSolvRNSMM (const enum SOLU_POS solupos, const long n, 
			      const long m, const long basislen, 
			      const FiniteField *basis, Double **ARNS, 
			      mpz_t *mp_B, mpz_t *mp_N, mpz_t mp_D);

/*
 * Calling Sequence:
 *   nonsingSolvRNSMM(solupos, basislen, n, m, basis, ARNS, mp_B, mp_N, mp_D)
 *
 * Summary:
 *   Solve nonsingular system of linear equations, where the left hand side 
 *   input matrix is represented in a RNS.
 *
 * Description:
 *   Given a n x n nonsingular matrix A represented in a RNS, a n x m or m x n
 *   mpz_t matrix mp_B, this function will compute the solution of the system
 *   1. AX = mp_B 
 *   2. XA = mp_B. 
 *   The parameter solupos controls whether the system is in the type of 1
 *   or 2.
 *   
 *   Since the unique solution X is a rational matrix, the function will
 *   output the numerator matrix mp_N and denominator mp_D respectively, 
 *   such that A(mp_N) = mp_D*mp_B or (mp_N)A = mp_D*mp_B. 
 *
 * Input: 
 *    solupos: enumerate, flag to indicate the system to be solved
 *           - solupos = LeftSolu: solve XA = mp_B
 *           - solupos = RightSolu: solve AX = mp_B
 *   basislen: long, dimension of RNS basis
 *          n: long, dimension of A
 *          m: long, column or row dimension of mp_B depending on solupos
 *      basis: 1-dim FiniteField array length basislen, RNS basis
 *       ARNS: 2-dim Double array, dimension basislen x n*n, representation of
 *             n x n input matrix A in RNS, where ARNS[i] = A mod basis[i]
 *       mp_B: 1-dim mpz_t array length n*m, representing the right hand side
 *             matrix of the system
 *           - solupos = LeftSolu: mp_B a m x n matrix
 *           - solupos = RightSolu: mp_B a n x m matrix
 * 
 * Output:
 *   mp_N: 1-dim mpz_t array length n*m, representing the numerator matrix 
 *         of the solution
 *       - solupos = LeftSolu: mp_N a m x n matrix
 *       - solupos = RightSolu: mp_N a n x m matrix
 *   mp_D: mpz_t, denominator of the solution
 *
 * Precondition: 
 *   - A must be a nonsingular matrix.
 *   - Any element p in RNS basis must satisfy 2*(p-1)^2 <= 2^53-1.
 *
 * Note:
 *   - It is necessary to make sure the input parameters are correct,
 *     expecially the dimension, since there is no parameter checks in the 
 *     function.
 *   - Input and output matrices are row majored and represented by
 *     one-dimension array.
 *   - It is needed to preallocate the memory space of mp_N and mp_D. 
 *
 */



extern long certSolveLong (const long certflag, const long n, const long m,
			   const long *A, mpz_t *mp_b, mpz_t *mp_N,
			   mpz_t mp_D, mpz_t *mp_NZ, mpz_t mp_DZ);

/*
 *
 * Calling Sequence:
 *   1/2/3 <-- certSolveLong(certflag, n, m, A, mp_b, mp_N, mp_D, 
 *                           mp_NZ, mp_DZ)
 * 
 * Summary:
 *   Certified solve a system of linear equations without reducing the 
 *   solution size, where the left hand side input matrix is represented 
 *   by signed long integers
 * 
 * Description:
 *   Let the system of linear equations be Av = b, where A is a n x m matrix,
 *   and b is a n x 1 vector. There are three possibilities:
 *
 *   1. The system has more than one rational solution
 *   2. The system has a unique rational solution
 *   3. The system has no solution
 *
 *   In the first case, there exist a solution vector v with minimal
 *   denominator and a rational certificate vector z to certify that the 
 *   denominator of solution v is really the minimal denominator.
 *
 *   The 1 x n certificate vector z satisfies that z.A is an integer vector 
 *   and z.b has the same denominator as the solution vector v.
 *   In this case, the function will output the solution with minimal 
 *   denominator and optional certificate vector z (if certflag = 1). 
 *
 *   Note: if choose not to compute the certificate vector z, the solution 
 *     will not garantee, but with high probability, to be the minimal 
 *     denominator solution, and the function will run faster.
 *
 *   In the second case, the function will only compute the unique solution 
 *   and the contents in the space for certificate vector make no sense.
 *
 *   In the third case, there exists a certificate vector q to certify that
 *   the system has no solution. The 1 x n vector q satisfies q.A = 0 but 
 *   q.b <> 0. In this case, the function will output this certificate vector
 *   q and store it into the same space for certificate z. The value of 
 *   certflag also controls whether to output q or not. 
 *  
 *   Note: if the function returns 3, then the system determinately does not 
 *     exist solution, no matter whether to output certificate q or not.
 * 
 * Input:
 *   certflag: 1/0, flag to indicate whether or not to compute the certificate 
 *             vector z or q. 
 *           - If certflag = 1, compute the certificate.
 *           - If certflag = 0, not compute the certificate.
 *          n: long, row dimension of the system
 *          m: long, column dimension of the system
 *          A: 1-dim signed long array length n*m, representation of n x m 
 *             matrix A
 *       mp_b: 1-dim mpz_t array length n, representation of n x 1 vector b
 *  
 * Return:
 *   1: the first case, system has more than one solution
 *   2: the second case, system has a unique solution
 *   3: the third case, system has no solution
 * 
 * Output:
 *   mp_N: 1-dim mpz_t array length m, 
 *       - numerator vector of the solution with minimal denominator 
 *         in the first case
 *       - numerator vector of the unique solution in the second case
 *       - make no sense in the third case
 *   mp_D: mpz_t,
 *       - minimal denominator of the solutions in the first case
 *       - denominator of the unique solution in the second case
 *       - make no sense in the third case
 *
 * The following will only be computed when certflag = 1
 *   mp_NZ: 1-dim mpz_t array length n, 
 *        - numerator vector of the certificate z in the first case
 *        - make no sense in the second case
 *        - numerator vector of the certificate q in the third case
 *   mp_DZ: mpz_t, 
 *        - denominator of the certificate z if in the first case
 *        - make no sense in the second case
 *        - denominator of the certificate q in the third case
 *
 * Note: 
 *   - The space of (mp_N, mp_D) is needed to be preallocated, and entries in
 *     mp_N and integer mp_D are needed to be initiated as any integer values.
 *   - If certflag is specified to be 1, then also needs to preallocate space
 *     for (mp_NZ, mp_DZ), and initiate integer mp_DZ and entries in mp_NZ to 
 *     be any integer values. 
 *     Otherwise, set mp_NZ = NULL, and mp_DZ = any integer
 *
 */



extern long certSolveRedLong (const long certflag, const long nullcol, 
			      const long n, const long m, const long *A,
			      mpz_t *mp_b, mpz_t *mp_N, mpz_t mp_D,
			      mpz_t *mp_NZ, mpz_t mp_DZ);

/*
 *
 * Calling Sequence:
 *   1/2/3 <-- certSolveRedLong(certflag, nullcol, n, m, A, mp_b, mp_N, mp_D, 
 *                              mp_NZ, mp_DZ)
 * 
 * Summary:
 *   Certified solve a system of linear equations and reduce the solution
 *   size, where the left hand side input matrix is represented by signed 
 *   long integers
 * 
 * Description:
 *   Let the system of linear equations be Av = b, where A is a n x m matrix,
 *   and b is a n x 1 vector. There are three possibilities:
 *
 *   1. The system has more than one rational solution
 *   2. The system has a unique rational solution
 *   3. The system has no solution
 *
 *   In the first case, there exist a solution vector v with minimal
 *   denominator and a rational certificate vector z to certify that the 
 *   denominator of solution v is really the minimal denominator.
 *
 *   The 1 x n certificate vector z satisfies that z.A is an integer vector 
 *   and z.b has the same denominator as the solution vector v.
 *   In this case, the function will output the solution with minimal 
 *   denominator and optional certificate vector z (if certflag = 1).