1 /** 2 * \file solve.h 3 * 4 * \brief System solving with matrix routines. 5 * 6 * \author Jean-Guillaume Dumas <Jean-Guillaume.Dumas@imag.fr> 7 * 8 */ 9 10 #ifndef M4RI_SOLVE_H 11 #define M4RI_SOLVE_H 12 13 /******************************************************************* 14 * 15 * M4RI: Linear Algebra over GF(2) 16 * 17 * Copyright (C) 2008 Jean-Guillaume.Dumas@imag.fr 18 * 19 * Distributed under the terms of the GNU General Public License (GPL) 20 * 21 * This code is distributed in the hope that it will be useful, 22 * but WITHOUT ANY WARRANTY; without even the implied warranty of 23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 24 * General Public License for more details. 25 * 26 * The full text of the GPL is available at: 27 * 28 * http://www.gnu.org/licenses/ 29 * 30 ********************************************************************/ 31 32 #include <m4ri/mzp.h> 33 #include <m4ri/mzd.h> 34 35 /** 36 * \brief Solves A X = B with A and B matrices. 37 * 38 * The solution X is stored inplace on B. 39 * 40 * \param A Input matrix (overwritten). 41 * \param B Input matrix, being overwritten by the solution matrix X 42 * \param cutoff Minimal dimension for Strassen recursion (default: 0). 43 * \param inconsistency_check decide wether or not to perform a check 44 * for incosistency (faster without but output not defined if 45 * system is not consistent). 46 * \return 0 if a solution was found, -1 otherwise 47 */ 48 int mzd_solve_left(mzd_t *A, mzd_t *B, int const cutoff, int const inconsistency_check); 49 50 /** 51 * \brief Solves (P L U Q) X = B 52 * 53 * A is an input matrix supposed to store both: 54 * \li an upper right triangular matrix U 55 * \li a lower left unitary triangular matrix L. 56 * 57 * The solution X is stored inplace on B 58 * 59 * This version assumes that the matrices are at an even position on 60 * the m4ri_radix grid and that their dimension is a multiple of m4ri_radix. 61 * 62 * \param A Input upper/lower triangular matrices. 63 * \param rank is rank of A. 64 * \param P Input row permutation matrix. 65 * \param Q Input column permutation matrix. 66 * \param B Input matrix, being overwritten by the solution matrix X. 67 * \param cutoff Minimal dimension for Strassen recursion (default: 0). 68 * \param inconsistency_check decide whether or not to perform a check 69 * for incosistency (faster without but output not defined if 70 * system is not consistent). \return 0 if a solution was 71 * found, -1 otherwise 72 * \return 0 if a solution was found, -1 otherwise 73 */ 74 int mzd_pluq_solve_left (mzd_t const *A, rci_t rank, 75 mzp_t const *P, mzp_t const *Q, 76 mzd_t *B, int const cutoff, int const inconsistency_check); 77 78 /** 79 * \brief Solves (P L U Q) X = B 80 * 81 * A is an input matrix supposed to store both: 82 * \li an upper right triangular matrix U 83 * \li a lower left unitary triangular matrix L. 84 85 * The solution X is stored inplace on B. 86 * 87 * This version assumes that the matrices are at an even position on 88 * the m4ri_radix grid and that their dimension is a multiple of m4ri_radix. 89 * 90 * \param A Input upper/lower triangular matrices. 91 * \param rank is rank of A. 92 * \param P Input row permutation matrix. 93 * \param Q Input column permutation matrix. 94 * \param B Input matrix, being overwritten by the solution matrix X. 95 * \param cutoff Minimal dimension for Strassen recursion (default: 0). 96 * \param inconsistency_check decide whether or not to perform a check 97 * for incosistency (faster without but output not defined if 98 * system is not consistent). \return 0 if a solution was 99 * found, -1 otherwise 100 * \return 0 if a solution was found, -1 otherwise 101 */ 102 int _mzd_pluq_solve_left(mzd_t const *A, rci_t rank, 103 mzp_t const *P, mzp_t const *Q, 104 mzd_t *B, int const cutoff, int const inconsistency_check); 105 106 /** 107 * \brief Solves A X = B with A and B matrices. 108 * 109 * The solution X is stored inplace on B. 110 * 111 * This version assumes that the matrices are at an even position on 112 * the m4ri_radix grid and that their dimension is a multiple of m4ri_radix. 113 * 114 * \param A Input matrix (overwritten). 115 * \param B Input matrix, being overwritten by the solution matrix X. 116 * \param cutoff Minimal dimension for Strassen recursion (default: 0). 117 * \param inconsistency_check decide whether or not to perform a check 118 * for incosistency (faster without but output not defined if 119 * system is not consistent). \return 0 if a solution was 120 * found, -1 otherwise 121 * \return 0 if a solution was found, -1 otherwise 122 */ 123 int _mzd_solve_left(mzd_t *A, mzd_t *B, int const cutoff, int const inconsistency_check); 124 125 /** 126 * \brief Solve X for A X = 0. 127 * 128 * If r is the rank of the nr x nc matrix A, return the nc x (nc-r) 129 * matrix X such that A*X == 0 and that the columns of X are linearly 130 * independent. 131 * 132 * \param A Input matrix (overwritten). 133 * \param cutoff Minimal dimension for Strassen recursion (default: 0). 134 * 135 * \sa mzd_pluq() 136 * 137 * \return X, NULL if kernel is empty 138 */ 139 140 mzd_t *mzd_kernel_left_pluq(mzd_t *A, int const cutoff); 141 142 #endif // M4RI_SOLVE_H 143