1.. _nmod-poly-mat: 2 3**nmod_poly_mat.h** -- matrices of univariate polynomials over integers mod n (word-size n) 4=========================================================================================== 5 6Description. 7 8Types, macros and constants 9------------------------------------------------------------------------------- 10 11.. type:: nmod_poly_mat_struct 12 13.. type:: nmod_poly_mat_t 14 15 Description. 16 17 18Memory management 19-------------------------------------------------------------------------------- 20 21 22.. function:: void nmod_poly_mat_init(nmod_poly_mat_t mat, slong rows, slong cols, mp_limb_t n) 23 24 Initialises a matrix with the given number of rows and columns for use. 25 The modulus is set to `n`. 26 27.. function:: void nmod_poly_mat_init_set(nmod_poly_mat_t mat, const nmod_poly_mat_t src) 28 29 Initialises a matrix ``mat`` of the same dimensions and modulus 30 as ``src``, and sets it to a copy of ``src``. 31 32.. function:: void nmod_poly_mat_clear(nmod_poly_mat_t mat) 33 34 Frees all memory associated with the matrix. The matrix must be 35 reinitialised if it is to be used again. 36 37 38Basic properties 39-------------------------------------------------------------------------------- 40 41 42.. function:: slong nmod_poly_mat_nrows(const nmod_poly_mat_t mat) 43 44 Returns the number of rows in ``mat``. 45 46.. function:: slong nmod_poly_mat_ncols(const nmod_poly_mat_t mat) 47 48 Returns the number of columns in ``mat``. 49 50.. function:: mp_limb_t nmod_poly_mat_modulus(const nmod_poly_mat_t mat) 51 52 Returns the modulus of ``mat``. 53 54 55Basic assignment and manipulation 56-------------------------------------------------------------------------------- 57 58 59.. function:: nmod_poly_struct * nmod_poly_mat_entry(const nmod_poly_mat_t mat, slong i, slong j) 60 61 Gives a reference to the entry at row ``i`` and column ``j``. 62 The reference can be passed as an input or output variable to any 63 ``nmod_poly`` function for direct manipulation of the matrix element. 64 No bounds checking is performed. 65 66.. function:: void nmod_poly_mat_set(nmod_poly_mat_t mat1, const nmod_poly_mat_t mat2) 67 68 Sets ``mat1`` to a copy of ``mat2``. 69 70.. function:: void nmod_poly_mat_swap(nmod_poly_mat_t mat1, nmod_poly_mat_t mat2) 71 72 Swaps ``mat1`` and ``mat2`` efficiently. 73 74 75 76Input and output 77-------------------------------------------------------------------------------- 78 79 80.. function:: void nmod_poly_mat_print(const nmod_poly_mat_t mat, const char * x) 81 82 Prints the matrix ``mat`` to standard output, using the 83 variable ``x``. 84 85 86Random matrix generation 87-------------------------------------------------------------------------------- 88 89 90.. function:: void nmod_poly_mat_randtest(nmod_poly_mat_t mat, flint_rand_t state, slong len) 91 92 This is equivalent to applying ``nmod_poly_randtest`` to all entries 93 in the matrix. 94 95.. function:: void nmod_poly_mat_randtest_sparse(nmod_poly_mat_t A, flint_rand_t state, slong len, float density) 96 97 Creates a random matrix with the amount of nonzero entries given 98 approximately by the ``density`` variable, which should be a fraction 99 between 0 (most sparse) and 1 (most dense). 100 101 The nonzero entries will have random lengths between 1 and ``len``. 102 103 104Special matrices 105-------------------------------------------------------------------------------- 106 107 108.. function:: void nmod_poly_mat_zero(nmod_poly_mat_t mat) 109 110 Sets ``mat`` to the zero matrix. 111 112.. function:: void nmod_poly_mat_one(nmod_poly_mat_t mat) 113 114 Sets ``mat`` to the unit or identity matrix of given shape, 115 having the element 1 on the main diagonal and zeros elsewhere. 116 If ``mat`` is nonsquare, it is set to the truncation of a unit matrix. 117 118 119Basic comparison and properties 120-------------------------------------------------------------------------------- 121 122 123.. function:: int nmod_poly_mat_equal(const nmod_poly_mat_t mat1, const nmod_poly_mat_t mat2) 124 125 Returns nonzero if ``mat1`` and ``mat2`` have the same shape and 126 all their entries agree, and returns zero otherwise. 127 128.. function:: int nmod_poly_mat_is_zero(const nmod_poly_mat_t mat) 129 130 Returns nonzero if all entries in ``mat`` are zero, and returns 131 zero otherwise. 132 133.. function:: int nmod_poly_mat_is_one(const nmod_poly_mat_t mat) 134 135 Returns nonzero if all entry of ``mat`` on the main diagonal 136 are the constant polynomial 1 and all remaining entries are zero, 137 and returns zero otherwise. The matrix need not be square. 138 139.. function:: int nmod_poly_mat_is_empty(const nmod_poly_mat_t mat) 140 141 Returns a non-zero value if the number of rows or the number of 142 columns in ``mat`` is zero, and otherwise returns 143 zero. 144 145.. function:: int nmod_poly_mat_is_square(const nmod_poly_mat_t mat) 146 147 Returns a non-zero value if the number of rows is equal to the 148 number of columns in ``mat``, and otherwise returns zero. 149 150 151 152Norms 153-------------------------------------------------------------------------------- 154 155 156.. function:: slong nmod_poly_mat_max_length(const nmod_poly_mat_t A) 157 158 Returns the maximum polynomial length among all the entries in ``A``. 159 160 161 162Evaluation 163-------------------------------------------------------------------------------- 164 165 166.. function:: void nmod_poly_mat_evaluate_nmod(nmod_mat_t B, const nmod_poly_mat_t A, mp_limb_t x) 167 168 Sets the ``nmod_mat_t`` ``B`` to ``A`` evaluated entrywise 169 at the point ``x``. 170 171 172 173Arithmetic 174-------------------------------------------------------------------------------- 175 176 177.. function:: void nmod_poly_mat_scalar_mul_nmod_poly(nmod_poly_mat_t B, const nmod_poly_mat_t A, const nmod_poly_t c) 178 179 Sets ``B`` to ``A`` multiplied entrywise by the polynomial ``c``. 180 181.. function:: void nmod_poly_mat_scalar_mul_nmod(nmod_poly_mat_t B, const nmod_poly_mat_t A, mp_limb_t c) 182 183 Sets ``B`` to ``A`` multiplied entrywise by the coefficient 184 ``c``, which is assumed to be reduced modulo the modulus. 185 186.. function:: void nmod_poly_mat_add(nmod_poly_mat_t C, const nmod_poly_mat_t A, const nmod_poly_mat_t B) 187 188 Sets ``C`` to the sum of ``A`` and ``B``. 189 All matrices must have the same shape. Aliasing is allowed. 190 191.. function:: void nmod_poly_mat_sub(nmod_poly_mat_t C, const nmod_poly_mat_t A, const nmod_poly_mat_t B) 192 193 Sets ``C`` to the sum of ``A`` and ``B``. 194 All matrices must have the same shape. Aliasing is allowed. 195 196.. function:: void nmod_poly_mat_neg(nmod_poly_mat_t B, const nmod_poly_mat_t A) 197 198 Sets ``B`` to the negation of ``A``. 199 The matrices must have the same shape. Aliasing is allowed. 200 201.. function:: void nmod_poly_mat_mul(nmod_poly_mat_t C, const nmod_poly_mat_t A, const nmod_poly_mat_t B) 202 203 Sets ``C`` to the matrix product of ``A`` and ``B``. 204 The matrices must have compatible dimensions for matrix multiplication. 205 Aliasing is allowed. This function automatically chooses between 206 classical, KS and evaluation-interpolation multiplication. 207 208.. function:: void nmod_poly_mat_mul_classical(nmod_poly_mat_t C, const nmod_poly_mat_t A, const nmod_poly_mat_t B) 209 210 Sets ``C`` to the matrix product of ``A`` and ``B``, 211 computed using the classical algorithm. The matrices must have 212 compatible dimensions for matrix multiplication. Aliasing is allowed. 213 214.. function:: void nmod_poly_mat_mul_KS(nmod_poly_mat_t C, const nmod_poly_mat_t A, const nmod_poly_mat_t B) 215 216 Sets ``C`` to the matrix product of ``A`` and ``B``, 217 computed using Kronecker segmentation. The matrices must have 218 compatible dimensions for matrix multiplication. Aliasing is allowed. 219 220.. function:: void nmod_poly_mat_mul_interpolate(nmod_poly_mat_t C, const nmod_poly_mat_t A, const nmod_poly_mat_t B) 221 222 Sets ``C`` to the matrix product of ``A`` and ``B``, 223 computed through evaluation and interpolation. The matrices must have 224 compatible dimensions for matrix multiplication. For interpolation 225 to be well-defined, we require that the modulus is a prime at least as 226 large as `m + n - 1` where `m` and `n` are the maximum lengths of 227 polynomials in the input matrices. Aliasing is allowed. 228 229.. function:: void nmod_poly_mat_sqr(nmod_poly_mat_t B, const nmod_poly_mat_t A) 230 231 Sets ``B`` to the square of ``A``, which must be a square matrix. 232 Aliasing is allowed. This function automatically chooses between 233 classical and KS squaring. 234 235.. function:: void nmod_poly_mat_sqr_classical(nmod_poly_mat_t B, const nmod_poly_mat_t A) 236 237 Sets ``B`` to the square of ``A``, which must be a square matrix. 238 Aliasing is allowed. This function uses direct formulas for very small 239 matrices, and otherwise classical matrix multiplication. 240 241.. function:: void nmod_poly_mat_sqr_KS(nmod_poly_mat_t B, const nmod_poly_mat_t A) 242 243 Sets ``B`` to the square of ``A``, which must be a square matrix. 244 Aliasing is allowed. This function uses Kronecker segmentation. 245 246.. function:: void nmod_poly_mat_sqr_interpolate(nmod_poly_mat_t B, const nmod_poly_mat_t A) 247 248 Sets ``B`` to the square of ``A``, which must be a square matrix, 249 computed through evaluation and interpolation. For interpolation 250 to be well-defined, we require that the modulus is a prime at least as 251 large as `2n - 1` where `n` is the maximum length of 252 polynomials in the input matrix. Aliasing is allowed. 253 254.. function:: void nmod_poly_mat_pow(nmod_poly_mat_t B, const nmod_poly_mat_t A, ulong exp) 255 256 Sets ``B`` to ``A`` raised to the power ``exp``, where ``A`` 257 is a square matrix. Uses exponentiation by squaring. Aliasing is allowed. 258 259 260Row reduction 261-------------------------------------------------------------------------------- 262 263 264.. function:: slong nmod_poly_mat_find_pivot_any(const nmod_poly_mat_t mat, slong start_row, slong end_row, slong c) 265 266 Attempts to find a pivot entry for row reduction. 267 Returns a row index `r` between ``start_row`` (inclusive) and 268 ``stop_row`` (exclusive) such that column `c` in ``mat`` has 269 a nonzero entry on row `r`, or returns -1 if no such entry exists. 270 271 This implementation simply chooses the first nonzero entry from 272 it encounters. This is likely to be a nearly optimal choice if all 273 entries in the matrix have roughly the same size, but can lead to 274 unnecessary coefficient growth if the entries vary in size. 275 276.. function:: slong nmod_poly_mat_find_pivot_partial(const nmod_poly_mat_t mat, slong start_row, slong end_row, slong c) 277 278 Attempts to find a pivot entry for row reduction. 279 Returns a row index `r` between ``start_row`` (inclusive) and 280 ``stop_row`` (exclusive) such that column `c` in ``mat`` has 281 a nonzero entry on row `r`, or returns -1 if no such entry exists. 282 283 This implementation searches all the rows in the column and 284 chooses the nonzero entry of smallest degree. This heuristic 285 typically reduces coefficient growth when the matrix entries 286 vary in size. 287 288.. function:: slong nmod_poly_mat_fflu(nmod_poly_mat_t B, nmod_poly_t den, slong * perm, const nmod_poly_mat_t A, int rank_check) 289 290 Uses fraction-free Gaussian elimination to set (``B``, ``den``) to a 291 fraction-free LU decomposition of ``A`` and returns the 292 rank of ``A``. Aliasing of ``A`` and ``B`` is allowed. 293 294 Pivot elements are chosen with ``nmod_poly_mat_find_pivot_partial``. 295 If ``perm`` is non-``NULL``, the permutation of 296 rows in the matrix will also be applied to ``perm``. 297 298 If ``rank_check`` is set, the function aborts and returns 0 if the 299 matrix is detected not to have full rank without completing the 300 elimination. 301 302 The denominator ``den`` is set to `\pm \operatorname{det}(A)`, where 303 the sign is decided by the parity of the permutation. Note that the 304 determinant is not generally the minimal denominator. 305 306.. function:: slong nmod_poly_mat_rref(nmod_poly_mat_t B, nmod_poly_t den, const nmod_poly_mat_t A) 307 308 Sets (``B``, ``den``) to the reduced row echelon form of ``A`` 309 and returns the rank of ``A``. 310 Aliasing of ``A`` and ``B`` is allowed. 311 312 The denominator ``den`` is set to `\pm \operatorname{det}(A)`. 313 Note that the determinant is not generally the minimal denominator. 314 315 316Trace 317-------------------------------------------------------------------------------- 318 319 320.. function:: void nmod_poly_mat_trace(nmod_poly_t trace, const nmod_poly_mat_t mat) 321 322 Computes the trace of the matrix, i.e. the sum of the entries on 323 the main diagonal. The matrix is required to be square. 324 325 326Determinant and rank 327-------------------------------------------------------------------------------- 328 329 330.. function:: void nmod_poly_mat_det(nmod_poly_t det, const nmod_poly_mat_t A) 331 332 Sets ``det`` to the determinant of the square matrix ``A``. Uses 333 a direct formula, fraction-free LU decomposition, or interpolation, 334 depending on the size of the matrix. 335 336.. function:: void nmod_poly_mat_det_fflu(nmod_poly_t det, const nmod_poly_mat_t A) 337 338 Sets ``det`` to the determinant of the square matrix ``A``. 339 The determinant is computed by performing a fraction-free LU 340 decomposition on a copy of ``A``. 341 342.. function:: void nmod_poly_mat_det_interpolate(nmod_poly_t det, const nmod_poly_mat_t A) 343 344 Sets ``det`` to the determinant of the square matrix ``A``. 345 The determinant is computed by determing a bound `n` for its length, 346 evaluating the matrix at `n` distinct points, computing the determinant 347 of each coefficient matrix, and forming the interpolating polynomial. 348 349 If the coefficient ring does not contain `n` distinct points (that is, 350 if working over `\mathbf{Z}/p\mathbf{Z}` where `p < n`), 351 this function automatically falls back to ``nmod_poly_mat_det_fflu``. 352 353.. function:: slong nmod_poly_mat_rank(const nmod_poly_mat_t A) 354 355 Returns the rank of ``A``. Performs fraction-free LU decomposition 356 on a copy of ``A``. 357 358 359 360Inverse 361-------------------------------------------------------------------------------- 362 363 364.. function:: int nmod_poly_mat_inv(nmod_poly_mat_t Ainv, nmod_poly_t den, const nmod_poly_mat_t A) 365 366 Sets (``Ainv``, ``den``) to the inverse matrix of ``A``. 367 Returns 1 if ``A`` is nonsingular and 0 if ``A`` is singular. 368 Aliasing of ``Ainv`` and ``A`` is allowed. 369 370 More precisely, ``det`` will be set to the determinant of ``A`` 371 and ``Ainv`` will be set to the adjugate matrix of ``A``. 372 Note that the determinant is not necessarily the minimal denominator. 373 374 Uses fraction-free LU decomposition, followed by solving for 375 the identity matrix. 376 377 378 379Nullspace 380-------------------------------------------------------------------------------- 381 382 383.. function:: slong nmod_poly_mat_nullspace(nmod_poly_mat_t res, const nmod_poly_mat_t mat) 384 385 Computes the right rational nullspace of the matrix ``mat`` and 386 returns the nullity. 387 388 More precisely, assume that ``mat`` has rank `r` and nullity `n`. 389 Then this function sets the first `n` columns of ``res`` 390 to linearly independent vectors spanning the nullspace of ``mat``. 391 As a result, we always have rank(``res``) `= n`, and 392 ``mat`` `\times` ``res`` is the zero matrix. 393 394 The computed basis vectors will not generally be in a reduced form. 395 In general, the polynomials in each column vector in the result 396 will have a nontrivial common GCD. 397 398 399Solving 400-------------------------------------------------------------------------------- 401 402 403.. function:: int nmod_poly_mat_solve(nmod_poly_mat_t X, nmod_poly_t den, const nmod_poly_mat_t A, const nmod_poly_mat_t B) 404 405 Solves the equation `AX = B` for nonsingular `A`. More precisely, computes 406 (``X``, ``den``) such that `AX = B \times \operatorname{den}`. 407 Returns 1 if `A` is nonsingular and 0 if `A` is singular. 408 The computed denominator will not generally be minimal. 409 410 Uses fraction-free LU decomposition followed by fraction-free 411 forward and back substitution. 412 413.. function:: int nmod_poly_mat_solve_fflu(nmod_poly_mat_t X, nmod_poly_t den, const nmod_poly_mat_t A, const nmod_poly_mat_t B) 414 415 Solves the equation `AX = B` for nonsingular `A`. More precisely, computes 416 (``X``, ``den``) such that `AX = B \times \operatorname{den}`. 417 Returns 1 if `A` is nonsingular and 0 if `A` is singular. 418 The computed denominator will not generally be minimal. 419 420 Uses fraction-free LU decomposition followed by fraction-free 421 forward and back substitution. 422 423.. function:: void nmod_poly_mat_solve_fflu_precomp(nmod_poly_mat_t X, const slong * perm, const nmod_poly_mat_t FFLU, const nmod_poly_mat_t B) 424 425 Performs fraction-free forward and back substitution given a precomputed 426 fraction-free LU decomposition and corresponding permutation. 427