libroutines

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

 *
 *   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.
 *
 *   Lattice reduction will be used to reduce the solution size. Parameter 
 *   nullcol designates the dimension of kernal basis we use to reduce the 
 *   solution size as well as the dimension of nullspace we use to compute 
 *   the minimal denominator. The heuristic results show that the solution 
 *   size will be reduced by factor 1/nullcol. 
 *
 *   To find the minimum denominator as fast as possible, nullcol cannot be
 *   too small. We use NULLSPACE_COLUMN as the minimal value of nullcol. That
 *   is, if the input nullcol is less than NULLSPACE_COLUMN, NULLSPACE_COLUMN
 *   will be used instead. However, if the input nullcol becomes larger, the
 *   function will be slower. Meanwhile, it does not make sense to make 
 *   nullcol greater than the dimension of nullspace of the input system. 
 *
 *   As a result, the parameter nullcol will not take effect unless 
 *   NULLSPACE_COLUMN < nullcol < dimnullspace is satisfied, where 
 *   dimnullspace is the dimension of nullspace of the input system.  If the
 *   above condition is not satisfied, the boundary value NULLSPACE_COLUMN or  
 *   dimnullspace will be used.
 *
 *   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.
 *    nullcol: long, dimension of nullspace and kernel basis of conditioned
 *             system, 
 *             if nullcol < NULLSPACE_COLUMN, use NULLSPACE_COLUMN instead
 *          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 certSolveMP (const long certflag, const long n, const long m,
			 mpz_t *mp_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 <-- certSolveMP(certflag, n, m, mp_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 mpz_t 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.
 *   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 the minimal denominator.
 * 
 * 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
 *       mp_A: 1-dim mpz_t 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 certSolveRedMP (const long certflag, const long nullcol,
			    const long n, const long m, mpz_t *mp_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 <-- certSolveRedMP(certflag, nullcol, n, m, mp_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 
 *   mpz_t 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.
 *
 *   Lattice reduction will be used to reduce the solution size. Parameter 
 *   nullcol designates the dimension of kernal basis we use to reduce the 
 *   solution size as well as the dimension of nullspace we use to compute 
 *   the minimal denominator. The heuristic results show that the solution 
 *   size will be reduced by factor 1/nullcol. 
 *
 *   To find the minimum denominator as fast as possible, nullcol cannot be
 *   too small. We use NULLSPACE_COLUMN as the minimal value of nullcol. That
 *   is, if the input nullcol is less than NULLSPACE_COLUMN, NULLSPACE_COLUMN
 *   will be used instead. However, if the input nullcol becomes larger, the
 *   function will be slower. Meanwhile, it does not make sense to make 
 *   nullcol greater than the dimension of nullspace of the input system. 
 *
 *   As a result, the parameter nullcol will not take effect unless 
 *   NULLSPACE_COLUMN < nullcol < dimnullspace is satisfied, where 
 *   dimnullspace is the dimension of nullspace of the input system.  If the
 *   above condition is not satisfied, the boundary value NULLSPACE_COLUMN or  
 *   dimnullspace will be used.
 *
 *   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.
 *   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 the minimal denominator.
 * 
 * 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.
 *    nullcol: long, dimension of nullspace and kernel basis of conditioned
 *             system, 
 *             if nullcol < NULLSPACE_COLUMN, use NULLSPACE_COLUMN instead
 *          n: long, row dimension of the system
 *          m: long, column dimension of the system
 *       mp_A: 1-dim mpz_t 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 void RowEchelonTransform (const FiniteField p, Double *A, const long n, 
				 const long m, const long frows,
				 const long lrows, const long redflag, 
				 const long eterm, long *Q, long *rp,
				 FiniteField *d);

/*
 * Calling Sequence:
 *   RowEchelonTransform(p, A, n, m, frows, lrows, redflag, eterm, Q, rp, d)