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