File: fmpz_mat.txt

package info (click to toggle)
flint 2.5.2-19
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 30,308 kB
  • sloc: ansic: 289,367; cpp: 11,210; python: 1,280; sh: 649; makefile: 283
file content (1238 lines) | stat: -rw-r--r-- 51,810 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
/*=============================================================================

    This file is part of FLINT.

    FLINT is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    FLINT is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with FLINT; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA

=============================================================================*/
/******************************************************************************

    Copyright (C) 2010 William Hart
    Copyright (C) 2010-2011 Andy Novocin
    Copyright (C) 2010-2011 Fredrik Johansson

******************************************************************************/


*******************************************************************************

    Memory management

*******************************************************************************

void fmpz_mat_init(fmpz_mat_t mat, slong rows, slong cols)

    Initialises a matrix with the given number of rows and columns for use. 

void fmpz_mat_clear(fmpz_mat_t mat)

    Clears the given matrix.

*******************************************************************************

    Basic assignment and manipulation

*******************************************************************************

void fmpz_mat_set(fmpz_mat_t mat1, const fmpz_mat_t mat2)

    Sets \code{mat1} to a copy of \code{mat2}. The dimensions of 
    \code{mat1} and \code{mat2} must be the same.

void fmpz_mat_init_set(fmpz_mat_t mat, const fmpz_mat_t src)

    Initialises the matrix \code{mat} to the same size as \code{src} and 
    sets it to a copy of \code{src}.

void fmpz_mat_swap(fmpz_mat_t mat1, fmpz_mat_t mat2)

    Swaps two matrices. The dimensions of \code{mat1} and \code{mat2} 
    are allowed to be different.

fmpz * fmpz_mat_entry(fmpz_mat_t mat, slong i, slong j)

    Returns a reference to the entry of \code{mat} at row $i$ and column $j$.
    This reference can be passed as an input or output variable to any
    function in the \code{fmpz} module for direct manipulation.

    Both $i$ and $j$ must not exceed the dimensions of the matrix.

    This function is implemented as a macro.

void fmpz_mat_zero(fmpz_mat_t mat)

    Sets all entries of \code{mat} to 0.

void fmpz_mat_one(fmpz_mat_t mat)

    Sets \code{mat} to the unit matrix, having ones on the main diagonal
    and zeroes elsewhere. If \code{mat} is nonsquare, it is set to the
    truncation of a unit matrix.

*******************************************************************************

    Window

*******************************************************************************

void fmpz_mat_window_init(fmpz_mat_t window, const fmpz_mat_t mat, slong r1,
                          slong c1, slong r2, slong c2)

    Initializes the matrix \code{window} to be an \code{r2 - r1} by
    \code{c2 - c1} submatrix of \code{mat} whose \code{(0,0)} entry
    is the \code{(r1, c1)} entry of \code{mat}. The memory for the
    elements of \code{window} is shared with \code{mat}.

void fmpz_mat_window_clear(fmpz_mat_t window)

    Clears the matrix \code{window} and releases any memory that it
    uses. Note that the memory to the underlying matrix that
    \code{window} points to is not freed.

*******************************************************************************

    Random matrix generation

*******************************************************************************

void fmpz_mat_randbits(fmpz_mat_t mat, flint_rand_t state, mp_bitcnt_t bits)

    Sets the entries of \code{mat} to random signed integers whose absolute 
    values have the given number of binary bits.

void fmpz_mat_randtest(fmpz_mat_t mat, flint_rand_t state, mp_bitcnt_t bits)

    Sets the entries of \code{mat} to random signed integers whose 
    absolute values have a random number of bits up to the given number 
    of bits inclusive.

void fmpz_mat_randintrel(fmpz_mat_t mat, flint_rand_t state, mp_bitcnt_t bits)

    Sets \code{mat} to be a random \emph{integer relations} matrix, with 
    signed entries up to the given number of bits.

    The number of columns of \code{mat} must be equal to one more than 
    the number of rows. The format of the matrix is a set of random integers 
    in the left hand column and an identity matrix in the remaining square 
    submatrix.

void fmpz_mat_randsimdioph(fmpz_mat_t mat, flint_rand_t state, 
                                           mp_bitcnt_t bits, mp_bitcnt_t bits2)

    Sets \code{mat} to a random \emph{simultaneous diophantine} matrix.

    The matrix must be square. The top left entry is set to \code{2^bits2}. 
    The remainder of that row is then set to signed random integers of the 
    given number of binary bits. The remainder of the first column is zero. 
    Running down the rest of the diagonal are the values \code{2^bits} with 
    all remaining entries zero.

void fmpz_mat_randntrulike(fmpz_mat_t mat, flint_rand_t state, 
                                                     mp_bitcnt_t bits, ulong q)

    Sets a square matrix \code{mat} of even dimension to a random 
    \emph{NTRU like} matrix.

    The matrix is broken into four square submatrices. The top left submatrix
    is set to the identity. The bottom left submatrix is set to the zero 
    matrix. The bottom right submatrix is set to $q$ times the identity matrix.
    Finally the top right submatrix has the following format. A random vector
    $h$ of length $r/2$ is created, with random signed entries of the given 
    number of bits. Then entry $(i, j)$ of the submatrix is set to 
    $h[i + j \bmod{r/2}]$. 

void fmpz_mat_randntrulike2(fmpz_mat_t mat, flint_rand_t state, 
                                                     mp_bitcnt_t bits, ulong q)

    Sets a square matrix \code{mat} of even dimension to a random 
    \emph{NTRU like} matrix.

    The matrix is broken into four square submatrices. The top left submatrix
    is set to $q$ times the identity matrix. The top right submatrix is set to 
    the zero matrix. The bottom right submatrix is set to the identity matrix.
    Finally the bottom left submatrix has the following format. A random vector
    $h$ of length $r/2$ is created, with random signed entries of the given 
    number of bits. Then entry $(i, j)$ of the submatrix is set to 
    $h[i + j \bmod{r/2}]$.

void fmpz_mat_randajtai(fmpz_mat_t mat, flint_rand_t state, double alpha)

    Sets a square matrix \code{mat} to a random \emph{ajtai} matrix. 
    The diagonal entries $(i, i)$ are set to a random entry in the range 
    $[1, 2^{b-1}]$ inclusive where $b = \floor{(2 r - i)^\alpha}$ for some 
    double parameter~$\alpha$. The entries below the diagonal in column~$i$ 
    are set to a random entry in the range $(-2^b + 1, 2^b - 1)$ whilst the 
    entries to the right of the diagonal in row~$i$ are set to zero. 

int fmpz_mat_randpermdiag(fmpz_mat_t mat, flint_rand_t state, 
                                                   const fmpz * diag, slong n)

    Sets \code{mat} to a random permutation of the rows and columns of a
    given diagonal matrix. The diagonal matrix is specified in the form of
    an array of the $n$ initial entries on the main diagonal.

    The return value is $0$ or $1$ depending on whether the permutation is
    even or odd.

void fmpz_mat_randrank(fmpz_mat_t mat, flint_rand_t state, slong rank, 
                                                              mp_bitcnt_t bits)

    Sets \code{mat} to a random sparse matrix with the given rank, 
    having exactly as many non-zero elements as the rank, with the 
    nonzero elements being random integers of the given bit size.

    The matrix can be transformed into a dense matrix with unchanged
    rank by subsequently calling \code{fmpz_mat_randops()}.

void fmpz_mat_randdet(fmpz_mat_t mat, flint_rand_t state, const fmpz_t det)

    Sets \code{mat} to a random sparse matrix with minimal number of
    nonzero entries such that its determinant has the given value.

    Note that the matrix will be zero if \code{det} is zero.  
    In order to generate a non-zero singular matrix, the function 
    \code{fmpz_mat_randrank()} can be used.

    The matrix can be transformed into a dense matrix with unchanged
    determinant by subsequently calling \code{fmpz_mat_randops()}.

void fmpz_mat_randops(fmpz_mat_t mat, flint_rand_t state, slong count)

    Randomises \code{mat} by performing elementary row or column operations.
    More precisely, at most \code{count} random additions or subtractions of
    distinct rows and columns will be performed. This leaves the rank
    (and for square matrices, the determinant) unchanged.


*******************************************************************************

    Input and output

*******************************************************************************

int fmpz_mat_fprint(FILE * file, const fmpz_mat_t mat)

    Prints the given matrix to the stream \code{file}.  The format is 
    the number of rows, a space, the number of columns, two spaces, then 
    a space separated list of coefficients, one row after the other.

    In case of success, returns a positive value;  otherwise, returns 
    a non-positive value.

int fmpz_mat_fprint_pretty(FILE * file, const fmpz_mat_t mat)

    Prints the given matrix to the stream \code{file}.  The format is an 
    opening square bracket then on each line a row of the matrix, followed 
    by a closing square bracket. Each row is written as an opening square 
    bracket followed by a space separated list of coefficients followed 
    by a closing square bracket.

    In case of success, returns a positive value;  otherwise, returns 
    a non-positive value.

int fmpz_mat_print(const fmpz_mat_t mat)

    Prints the given matrix to the stream \code{stdout}.  For further 
    details, see \code{fmpz_mat_fprint()}.

int fmpz_mat_print_pretty(const fmpz_mat_t mat)

    Prints the given matrix to \code{stdout}.  For further details, 
    see \code{fmpz_mat_fprint_pretty()}.

int fmpz_mat_fread(FILE* file, fmpz_mat_t mat)

    Reads a matrix from the stream \code{file}, storing the result 
    in \code{mat}.  The expected format is the number of rows, a 
    space, the number of columns, two spaces, then a space separated
    list of coefficients, one row after the other.

    In case of success, returns a positive number.  In case of failure, 
    returns a non-positive value.

int fmpz_mat_read(fmpz_mat_t mat)

    Reads a matrix from \code{stdin}, storing the result 
    in \code{mat}.

    In case of success, returns a positive number.  In case of failure, 
    returns a non-positive value.

*******************************************************************************

    Comparison

*******************************************************************************

int fmpz_mat_equal(const fmpz_mat_t mat1, const fmpz_mat_t mat2)

    Returns a non-zero value if \code{mat1} and \code{mat2} have 
    the same dimensions and entries, and zero otherwise.

int fmpz_mat_is_zero(const fmpz_mat_t mat)

    Returns a non-zero value if all entries \code{mat} are zero, and
    otherwise returns zero.

int fmpz_mat_is_one(const fmpz_mat_t mat)

    Returns a non-zero value if \code{mat} is the unit matrix or the truncation
    of a unit matrix, and otherwise returns zero.

int fmpz_mat_is_empty(const fmpz_mat_t mat)

    Returns a non-zero value if the number of rows or the number of
    columns in \code{mat} is zero, and otherwise returns
    zero.

int fmpz_mat_is_square(const fmpz_mat_t mat)

    Returns a non-zero value if the number of rows is equal to the
    number of columns in \code{mat}, and otherwise returns zero.

*******************************************************************************

    Transpose

*******************************************************************************

void fmpz_mat_transpose(fmpz_mat_t B, const fmpz_mat_t A)

    Sets $B$ to $A^T$, the transpose of $A$. Dimensions must be compatible.
    $A$ and $B$ are allowed to be the same object if $A$ is a square matrix.


*******************************************************************************

    Concatenate

*******************************************************************************

void fmpz_mat_concat_vertical(fmpz_mat_t res, const fmpz_mat_t mat1, 
                                                         const fmpz_mat_t mat2)
    Sets \code{res} to vertical concatenation of (\code{mat1}, \code{mat2})
    in that order.
    Matrix dimensions :
    \code{mat1} : $m \times n$, 
    \code{mat2} : $k \times n$, 
    \code{res} : $(m + k) \times n$.

void fmpz_mat_concat_horizontal(fmpz_mat_t res, const fmpz_mat_t mat1,
                                                         const fmpz_mat_t mat2)
    Sets \code{res} to horizontal concatenation of (\code{mat1}, \code{mat2})
    in that order.
    Matrix dimensions :
    \code{mat1} : $m \times n$, 
    \code{mat2} : $m \times k$, 
    \code{res}  : $m \times (n + k)$.

*******************************************************************************

    Modular reduction and reconstruction

*******************************************************************************

void fmpz_mat_get_nmod_mat(nmod_mat_t Amod, const fmpz_mat_t A)

    Sets the entries of \code{Amod} to the entries of \code{A} reduced
    by the modulus of \code{Amod}.

void fmpz_mat_set_nmod_mat(fmpz_mat_t A, const nmod_mat_t Amod)

    Sets the entries of \code{Amod} to the residues in \code{Amod},
    normalised to the interval $-m/2 <= r < m/2$ where $m$ is the modulus.

void fmpz_mat_set_nmod_mat_unsigned(fmpz_mat_t A, const nmod_mat_t Amod)

    Sets the entries of \code{Amod} to the residues in \code{Amod},
    normalised to the interval $0 <= r < m$ where $m$ is the modulus.

void fmpz_mat_CRT_ui(fmpz_mat_t res, const fmpz_mat_t mat1,
                        const fmpz_t m1, const nmod_mat_t mat2, int sign)

    Given \code{mat1} with entries modulo \code{m} and \code{mat2}
    with modulus $n$, sets \code{res} to the CRT reconstruction modulo $mn$
    with entries satisfying $-mn/2 <= c < mn/2$ (if sign = 1)
    or $0 <= c < mn$ (if sign = 0).

void fmpz_mat_multi_mod_ui_precomp(nmod_mat_t * residues, slong nres, 
    const fmpz_mat_t mat, fmpz_comb_t comb, fmpz_comb_temp_t temp)

    Sets each of the \code{nres} matrices in \code{residues} to \code{mat}
    reduced modulo the modulus of the respective matrix, given
    precomputed \code{comb} and \code{comb_temp} structures.

void fmpz_mat_multi_mod_ui(nmod_mat_t * residues, slong nres,
        const fmpz_mat_t mat)

    Sets each of the \code{nres} matrices in \code{residues} to \code{mat}
    reduced modulo the modulus of the respective matrix.

    This function is provided for convenience purposes.
    For reducing or reconstructing multiple integer matrices over the same
    set of moduli, it is faster to use\\ \code{fmpz_mat_multi_mod_precomp}.

void fmpz_mat_multi_CRT_ui_precomp(fmpz_mat_t mat, nmod_mat_t * const residues,
    slong nres, fmpz_comb_t comb, fmpz_comb_temp_t temp, int sign)

    Reconstructs \code{mat} from its images modulo the \code{nres} matrices
    in \code{residues}, given precomputed \code{comb} and \code{comb_temp}
    structures.

void fmpz_mat_multi_CRT_ui(fmpz_mat_t mat, nmod_mat_t * const residues,
    slong nres, int sign)

    Reconstructs \code{mat} from its images modulo the \code{nres} matrices
    in \code{residues}.

    This function is provided for convenience purposes.
    For reducing or reconstructing multiple integer matrices over the same
    set of moduli, it is faster to use\\ \code{fmpz_mat_multi_CRT_ui_precomp}.

*******************************************************************************

    Addition and subtraction

*******************************************************************************

void fmpz_mat_add(fmpz_mat_t C, const fmpz_mat_t A, const fmpz_mat_t B)

    Sets \code{C} to the elementwise sum $A + B$. All inputs must
    be of the same size. Aliasing is allowed.

void fmpz_mat_sub(fmpz_mat_t C, const fmpz_mat_t A, const fmpz_mat_t B)

    Sets \code{C} to the elementwise difference $A - B$. All inputs must
    be of the same size. Aliasing is allowed.

void fmpz_mat_neg(fmpz_mat_t B, const fmpz_mat_t A)

    Sets \code{B} to the elementwise negation of \code{A}. Both inputs
    must be of the same size. Aliasing is allowed.

*******************************************************************************

    Matrix-scalar arithmetic

*******************************************************************************

void fmpz_mat_scalar_mul_si(fmpz_mat_t B, const fmpz_mat_t A, slong c)

void fmpz_mat_scalar_mul_ui(fmpz_mat_t B, const fmpz_mat_t A, ulong c)

void fmpz_mat_scalar_mul_fmpz(fmpz_mat_t B, const fmpz_mat_t A, const fmpz_t c)

    Set \code{A = B*c} where \code{B} is an \code{fmpz_mat_t} and \code{c}
    is a scalar respectively of type \code{slong}, \code{ulong},
    or \code{fmpz_t}. The dimensions of \code{A} and \code{B} must
    be compatible.

void fmpz_mat_scalar_addmul_si(fmpz_mat_t B, const fmpz_mat_t A, slong c)

void fmpz_mat_scalar_addmul_ui(fmpz_mat_t B, const fmpz_mat_t A, ulong c)

void fmpz_mat_scalar_addmul_fmpz(fmpz_mat_t B, const fmpz_mat_t A,
                                    const fmpz_t c)

    Set \code{A = A + B*c} where \code{B} is an \code{fmpz_mat_t} and \code{c}
    is a scalar respectively of type \code{slong}, \code{ulong},
    or \code{fmpz_t}. The dimensions of \code{A} and \code{B} must
    be compatible.

void fmpz_mat_scalar_submul_si(fmpz_mat_t B, const fmpz_mat_t A, slong c)

void fmpz_mat_scalar_submul_ui(fmpz_mat_t B, const fmpz_mat_t A, ulong c)

void fmpz_mat_scalar_submul_fmpz(fmpz_mat_t B, const fmpz_mat_t A,
                                    const fmpz_t c)

    Set \code{A = A - B*c} where \code{B} is an \code{fmpz_mat_t} and \code{c}
    is a scalar respectively of type \code{slong}, \code{ulong},
    or \code{fmpz_t}. The dimensions of \code{A} and \code{B} must
    be compatible.

void fmpz_mat_scalar_addmul_nmod_mat_ui(fmpz_mat_t B, const nmod_mat_t A,
                                    ulong c)
void fmpz_mat_scalar_addmul_nmod_mat_fmpz(fmpz_mat_t B, const nmod_mat_t A,
                                    const fmpz_t c)

    Set \code{A = A + B*c} where \code{B} is an \code{nmod_mat_t} and \code{c}
    is a scalar respectively of type \code{ulong} or \code{fmpz_t}.
    The dimensions of \code{A} and \code{B} must be compatible.

void fmpz_mat_scalar_divexact_si(fmpz_mat_t B, const fmpz_mat_t A, slong c)

void fmpz_mat_scalar_divexact_ui(fmpz_mat_t B, const fmpz_mat_t A, ulong c)

void fmpz_mat_scalar_divexact_fmpz(fmpz_mat_t B, const fmpz_mat_t A,
                                    const fmpz_t c)

    Set \code{A = B / c}, where \code{B} is an \code{fmpz_mat_t} and \code{c}
    is a scalar respectively of type \code{slong}, \code{ulong},
    or \code{fmpz_t}, which is assumed to divide all elements of
    \code{B} exactly.

void fmpz_mat_scalar_mul_2exp(fmpz_mat_t B, const fmpz_mat_t A, ulong exp)

    Set the matrix \code{B} to the matrix \code{A}, of the same dimensions,
    multiplied by $2^{exp}$.

void fmpz_mat_scalar_tdiv_q_2exp(fmpz_mat_t B, const fmpz_mat_t A, ulong exp)

    Set the matrix \code{B} to the matrix \code{A}, of the same dimensions,
    divided by $2^{exp}$, rounding down towards zero.


*******************************************************************************

    Matrix multiplication

*******************************************************************************

void fmpz_mat_mul(fmpz_mat_t C, const fmpz_mat_t A, const fmpz_mat_t B)

    Sets \code{C} to the matrix product $C = A B$. The matrices must have
    compatible dimensions for matrix multiplication. Aliasing
    is allowed.

    This function automatically switches between classical and
    multimodular multiplication, based on a heuristic comparison of
    the dimensions and entry sizes.

void fmpz_mat_mul_classical(fmpz_mat_t C, 
                                        const fmpz_mat_t A, const fmpz_mat_t B)

    Sets \code{C} to the matrix product $C = A B$ computed using
    classical matrix algorithm.

    The matrices must have compatible dimensions for matrix multiplication.
    No aliasing is allowed.

void _fmpz_mat_mul_multi_mod(fmpz_mat_t C,
            const fmpz_mat_t A, const fmpz_mat_t B, mp_bitcnt_t bits)

void fmpz_mat_mul_multi_mod(fmpz_mat_t C,
            const fmpz_mat_t A, const fmpz_mat_t B)

    Sets \code{C} to the matrix product $C = AB$ computed using a multimodular 
    algorithm. $C$ is computed modulo several small prime numbers
    and reconstructed using the Chinese Remainder Theorem. This generally
    becomes more efficient than classical multiplication for large matrices.

    The \code{bits} parameter is a bound for the bit size of largest 
    element of $C$, or twice the absolute value of the largest element 
    if any elements of $C$ are negative. The function
    \code{fmpz_mat_mul_multi_mod} calculates a rigorous bound automatically.
    If the default bound is too pessimistic, \code{_fmpz_mat_mul_multi_mod}
    can be used with a custom bound.

    The matrices must have compatible dimensions for matrix multiplication.
    No aliasing is allowed.

void fmpz_mat_sqr(fmpz_mat_t B, const fmpz_mat_t A)

    Sets \code{B} to the square of the matrix \code{A}, which must be
    a square matrix. Aliasing is allowed.
    The function calls \code{fmpz_mat_mul} for dimensions less than 12 and
    calls \code{fmpz_mat_sqr_bodrato} for cases in which the latter is faster.

void fmpz_mat_sqr_bodrato(fmpz_mat_t B, const fmpz_mat_t A)

    Sets \code{B} to the square of the matrix \code{A}, which must be
    a square matrix. Aliasing is allowed.
    The bodrato algorithm is described in \cite{Bodrato2010}.
    It is highly efficient for squaring matrices which satisfy both the 
    following conditions  : (a) large elements  (b) dimensions less than 150.


void fmpz_mat_pow(fmpz_mat_t B, const fmpz_mat_t A, ulong e)

    Sets \code{B} to the matrix \code{A} raised to the power \code{e},
    where \code{A} must be a square matrix. Aliasing is allowed.


*******************************************************************************

    Inverse

*******************************************************************************

int fmpz_mat_inv(fmpz_mat_t Ainv, fmpz_t den, const fmpz_mat_t A)

    Sets (\code{Ainv}, \code{den}) to the inverse matrix of \code{A}.
    Returns 1 if \code{A} is nonsingular and 0 if \code{A} is singular.
    Aliasing of \code{Ainv} and \code{A} is allowed.

    The denominator is not guaranteed to be minimal, but is guaranteed
    to be a divisor of the determinant of \code{A}.

    This function uses a direct formula for matrices of size two or less,
    and otherwise solves for the identity matrix using
    fraction-free LU decomposition.


*******************************************************************************

    Content

*******************************************************************************

void fmpz_mat_content(fmpz_t mat_gcd, const fmpz_mat_t A)

    Sets \code{mat_gcd} as the gcd of all the elements of the matrix \code{A}.
    Returns 0 if the matrix is empty. 
    

*******************************************************************************

    Trace

*******************************************************************************

void fmpz_mat_trace(fmpz_t trace, const fmpz_mat_t mat)

    Computes the trace of the matrix, i.e. the sum of the entries on
    the main diagonal. The matrix is required to be square.


*******************************************************************************

    Determinant

*******************************************************************************

void fmpz_mat_det(fmpz_t det, const fmpz_mat_t A)

    Sets \code{det} to the determinant of the square matrix $A$.
    The matrix of dimension $0 \times 0$ is defined to have determinant 1.

    This function automatically chooses between \code{fmpz_mat_det_cofactor},\\
    \code{fmpz_mat_det_bareiss}, \code{fmpz_mat_det_modular} and\\
    \code{fmpz_mat_det_modular_accelerated}
    (with \code{proved} = 1), depending on the size of the matrix
    and its entries.

void fmpz_mat_det_cofactor(fmpz_t det, const fmpz_mat_t A)

    Sets \code{det} to the determinant of the square matrix $A$
    computed using direct cofactor expansion. This function only
    supports matrices up to size $4 \times 4$.

void fmpz_mat_det_bareiss(fmpz_t det, const fmpz_mat_t A)

    Sets \code{det} to the determinant of the square matrix $A$
    computed using the Bareiss algorithm. A copy of the input matrix is
    row reduced using fraction-free Gaussian elimination, and the
    determinant is read off from the last element on the main
    diagonal.

void fmpz_mat_det_modular(fmpz_t det, const fmpz_mat_t A, int proved)

    Sets \code{det} to the determinant of the square matrix $A$
    (if \code{proved} = 1), or a probabilistic value for the
    determinant (\code{proved} = 0), computed using a multimodular
    algorithm.

    The determinant is computed modulo several small primes and
    reconstructed using the Chinese Remainder Theorem.
    With \code{proved} = 1, sufficiently many primes are chosen
    to satisfy the bound computed by \code{fmpz_mat_det_bound}.
    With \code{proved} = 0, the determinant is considered determined
    if it remains unchanged modulo several consecutive primes
    (currently if their product exceeds $2^{100}$).

void fmpz_mat_det_modular_accelerated(fmpz_t det,
        const fmpz_mat_t A, int proved)

    Sets \code{det} to the determinant of the square matrix $A$
    (if \code{proved} = 1), or a probabilistic value for the
    determinant (\code{proved} = 0), computed using a multimodular
    algorithm.

    This function uses the same basic algorithm as \code{fmpz_mat_det_modular},
    but instead of computing $\det(A)$ directly, it generates a divisor $d$
    of $\det(A)$ and then computes $x = \det(A) / d$ modulo several
    small primes not dividing $d$. This typically accelerates the
    computation by requiring fewer primes for large matrices, since $d$
    with high probability will be nearly as large as the determinant.
    This trick is described in \citep{AbbottBronsteinMulders1999}.

void fmpz_mat_det_modular_given_divisor(fmpz_t det, const fmpz_mat_t A,
        const fmpz_t d, int proved)

    Given a positive divisor $d$ of $\det(A)$, sets \code{det} to the
    determinant of the square matrix $A$ (if \code{proved} = 1), or a
    probabilistic value for the determinant (\code{proved} = 0), computed
    using a multimodular algorithm.

void fmpz_mat_det_bound(fmpz_t bound, const fmpz_mat_t A)

    Sets \code{bound} to a nonnegative integer $B$ such that
    $|\det(A)| \le B$. Assumes $A$ to be a square matrix.
    The bound is computed from the Hadamard inequality
    $|\det(A)| \le \prod \|a_i\|_2$ where the product is taken
    over the rows $a_i$ of $A$.

void fmpz_mat_det_divisor(fmpz_t d, const fmpz_mat_t A)

    Sets $d$ to some positive divisor of the determinant of the given
    square matrix $A$, if the determinant is nonzero. If $|\det(A)| = 0$,
    $d$ will always be set to zero.

    A divisor is obtained by solving $Ax = b$ for an arbitrarily chosen
    right-hand side $b$ using Dixon's algorithm and computing the least
    common multiple of the denominators in $x$. This yields a divisor $d$
    such that $|\det(A)| / d$ is tiny with very high probability.


*******************************************************************************

    Characteristic polynomial

*******************************************************************************

void _fmpz_mat_charpoly(fmpz * cp, const fmpz_mat_t mat)

    Sets \code{(cp, n+1)} to the characteristic polynomial of 
    an $n \times n$ square matrix.

void fmpz_mat_charpoly(fmpz_poly_t cp, const fmpz_mat_t mat)

    Computes the characteristic polynomial of length $n + 1$ of 
    an $n \times n$ square matrix.

*******************************************************************************

    Rank

*******************************************************************************

slong fmpz_mat_rank(const fmpz_mat_t A)

    Returns the rank, that is, the number of linearly independent columns
    (equivalently, rows), of $A$. The rank is computed by row reducing
    a copy of $A$.


*******************************************************************************

    Nonsingular solving

    The following functions allow solving matrix-matrix equations $AX = B$
    where the system matrix $A$ is square and has full rank. The solving
    is implicitly done over the field of rational numbers: except
    where otherwise noted, an integer matrix $\hat X$ and a separate
    denominator $d$ (\code{den}) are computed such that $A(\hat X/d) = b$,
    equivalently such that $A\hat X = bd$ holds over the integers.

    No guarantee is made that the numerators and denominator
    are reduced to lowest terms, but the denominator is always guaranteed
    to be a divisor of the determinant of $A$. If $A$ is singular,
    \code{den} will be set to zero and the elements of the solution
    vector or matrix will have undefined values. No aliasing is
    allowed between arguments.

*******************************************************************************

int fmpz_mat_solve(fmpz_mat_t X, fmpz_t den,
                    const fmpz_mat_t A, const fmpz_mat_t B)

    Solves the equation $AX = B$ for nonsingular $A$. More precisely, computes
    (\code{X}, \code{den}) such that $AX = B \times \operatorname{den}$.
    Returns 1 if $A$ is nonsingular and 0 if $A$ is singular.
    The computed denominator will not generally be minimal.

    This function uses Cramer's rule for small systems and
    fraction-free LU decomposition followed by fraction-free forward
    and back substitution for larger systems.

    Note that for very large systems, it is faster to compute a modular
    solution using \code{fmpz_mat_solve_dixon}.

int fmpz_mat_solve_fflu(fmpz_mat_t X, fmpz_t den,
                            const fmpz_mat_t A, const fmpz_mat_t B)

    Solves the equation $AX = B$ for nonsingular $A$. More precisely, computes
    (\code{X}, \code{den}) such that $AX = B \times \operatorname{den}$.
    Returns 1 if $A$ is nonsingular and 0 if $A$ is singular.
    The computed denominator will not generally be minimal.

    Uses fraction-free LU decomposition followed by fraction-free
    forward and back substitution.

void fmpz_mat_solve_fflu_precomp(fmpz_mat_t X,
                    const slong * perm,
                    const fmpz_mat_t FFLU, const fmpz_mat_t B)

    Performs fraction-free forward and back substitution given a precomputed
    fraction-free LU decomposition and corresponding permutation.

int fmpz_mat_solve_cramer(fmpz_mat_t X, fmpz_t den,
                            const fmpz_mat_t A, const fmpz_mat_t B)

    Solves the equation $AX = B$ for nonsingular $A$. More precisely, computes
    (\code{X}, \code{den}) such that $AX = B \times \operatorname{den}$.
    Returns 1 if $A$ is nonsingular and 0 if $A$ is singular.

    Uses Cramer's rule. Only systems of size up to $3 \times 3$ are allowed.

void fmpz_mat_solve_bound(fmpz_t N, fmpz_t D, const fmpz_mat_t A,
    const fmpz_mat_t B)

    Assuming that $A$ is nonsingular, computes integers $N$ and $D$
    such that the reduced numerators and denominators $n/d$ in
    $A^{-1} B$ satisfy the bounds $0 \le |n| \le N$ and $0 \le d \le D$.

int fmpz_mat_solve_dixon(fmpz_mat_t X, fmpz_t M, const fmpz_mat_t A,
        const fmpz_mat_t B)

    Solves $AX = B$ given a nonsingular square matrix $A$ and a matrix $B$ of
    compatible dimensions, using a modular algorithm. In particular,
    Dixon's p-adic lifting algorithm is used (currently a non-adaptive version).
    This is generally the preferred method for large dimensions.

    More precisely, this function computes an integer $M$ and an integer
    matrix $X$ such that $AX = B \bmod M$ and such that all the reduced
    numerators and denominators of the elements $x = p/q$ in the full
    solution satisfy $2|p|q < M$. As such, the explicit rational solution
    matrix can be recovered uniquely by passing the output of this
    function to \code{fmpq_mat_set_fmpz_mat_mod}.

    A nonzero value is returned if $A$ is nonsingular. If $A$ is singular,
    zero is returned and the values of the output variables will be
    undefined.

    Aliasing between input and output matrices is allowed.

*******************************************************************************

    Row reduction

*******************************************************************************

slong fmpz_mat_find_pivot_any(const fmpz_mat_t mat,
                                    slong start_row, slong end_row, slong c)

    Attempts to find a pivot entry for row reduction.
    Returns a row index $r$ between \code{start_row} (inclusive) and
    \code{stop_row} (exclusive) such that column $c$ in \code{mat} has
    a nonzero entry on row $r$, or returns -1 if no such entry exists.

    This implementation simply chooses the first nonzero entry from
    it encounters. This is likely to be a nearly optimal choice if all
    entries in the matrix have roughly the same size, but can lead to
    unnecessary coefficient growth if the entries vary in size.

slong fmpz_mat_fflu(fmpz_mat_t B, fmpz_t den, slong * perm,
                            const fmpz_mat_t A, int rank_check)

    Uses fraction-free Gaussian elimination to set (\code{B}, \code{den}) to a
    fraction-free LU decomposition of \code{A} and returns the
    rank of \code{A}. Aliasing of \code{A} and \code{B} is allowed.

    Pivot elements are chosen with \code{fmpz_mat_find_pivot_any}.
    If \code{perm} is non-\code{NULL}, the permutation of
    rows in the matrix will also be applied to \code{perm}.

    If \code{rank_check} is set, the function aborts and returns 0 if the
    matrix is detected not to have full rank without completing the
    elimination.

    The denominator \code{den} is set to $\pm \operatorname{det}(S)$ where
    $S$ is an appropriate submatrix of $A$ ($S = A$ if $A$ is square)
    and the sign is decided by the parity of the permutation. Note that the
    determinant is not generally the minimal denominator.

    The fraction-free LU decomposition is defined in \citep{NakTurWil1997}.

slong fmpz_mat_rref(fmpz_mat_t B, fmpz_t den, const fmpz_mat_t A)

    Sets (\code{B}, \code{den}) to the reduced row echelon form of \code{A}
    and returns the rank of \code{A}. Aliasing of \code{A} and \code{B}
    is allowed.

    The algorithm used chooses between \code{fmpz_mat_rref_fflu} and
    \code{fmpz_mat_rref_mul} based on the dimensions of the input matrix.

slong fmpz_mat_rref_fflu(fmpz_mat_t B, fmpz_t den, const fmpz_mat_t A)

    Sets (\code{B}, \code{den}) to the reduced row echelon form of \code{A}
    and returns the rank of \code{A}. Aliasing of \code{A} and \code{B}
    is allowed.

    The algorithm proceeds by first computing a row echelon form using
    \code{fmpz_mat_fflu}. Letting the upper part of this matrix be
    $(U | V) P$ where $U$ is full rank upper triangular and $P$ is a
    permutation matrix, we obtain the rref by setting $V$ to $U^{-1} V$
    using back substitution. Scaling each completed row in the back
    substitution to the denominator \code{den}, we avoid introducing
    new fractions. This strategy is equivalent to the fraction-free
    Gauss-Jordan elimination in \citep{NakTurWil1997}, but faster since
    only the part $V$ corresponding to the null space has to be updated.

    The denominator \code{den} is set to $\pm \operatorname{det}(S)$ where
    $S$ is an appropriate submatrix of $A$ ($S = A$ if $A$ is square).
    Note that the determinant is not generally the minimal denominator.

slong fmpz_mat_rref_mul(fmpz_mat_t B, fmpz_t den, const fmpz_mat_t A)

    Sets (\code{B}, \code{den}) to the reduced row echelon form of \code{A}
    and returns the rank of \code{A}. Aliasing of \code{A} and \code{B}
    is allowed.

    The algorithm works by computing the reduced row echelon form of \code{A}
    modulo a prime $p$ using \code{nmod_mat_rref}. The pivot columns and rows
    of this matrix will then define a non-singular submatrix of \code{A},
    nonsingular solving and matrix multiplication can then be used to determine 
    the reduced row echelon form of the whole of \code{A}. This procedure is
    described in \cite{Stein2007}.

int fmpz_mat_is_in_rref_with_rank(const fmpz_mat_t A, const fmpz_t den,
                                   slong rank)

    Checks that the matrix $A/den$ is in reduced row echelon form of rank 
    \code{rank}, returns 1 if so and 0 otherwise.

*******************************************************************************

    Modular gaussian elimination

*******************************************************************************

slong fmpz_mat_rref_mod(slong * perm, fmpz_mat_t A, const fmpz_t p)

    Uses fraction-free Gauss-Jordan elimination to set \code{A}
    to its reduced row echelon form and returns the rank of \code{A}.
    All computations are done modulo p.

    Pivot elements are chosen with \code{fmpz_mat_find_pivot_any}.
    If \code{perm} is non-\code{NULL}, the permutation of
    rows in the matrix will also be applied to \code{perm}.

*******************************************************************************

    Nullspace

*******************************************************************************

slong fmpz_mat_nullspace(fmpz_mat_t B, const fmpz_mat_t A)

    Computes a basis for the right rational nullspace of $A$ and returns
    the dimension of the nullspace (or nullity). $B$ is set to a matrix with
    linearly independent columns and maximal rank such that $AB = 0$
    (i.e. $Ab = 0$ for each column $b$ in $B$), and the rank of $B$ is
    returned.

    In general, the entries in $B$ will not be minimal: in particular,
    the pivot entries in $B$ will generally differ from unity.
    $B$ must be allocated with sufficient space to represent the result
    (at most $n \times n$ where $n$ is the number of column of $A$).


*******************************************************************************

    Echelon form

*******************************************************************************

slong fmpz_mat_rref_fraction_free(slong * perm, fmpz_mat_t B, fmpz_t den,
        const fmpz_mat_t A)

    Computes an integer matrix \code{B} and an integer \code{den} such that
    \code{B / den} is the unique row reduced echelon form (RREF) of \code{A}
    and returns the rank, i.e. the number of nonzero rows in \code{B}.

    Aliasing of \code{B} and \code{A} is allowed, with an in-place
    computation being more efficient. The size of \code{B} must be
    the same as that of \code{A}.

    The permutation order will be written to \code{perm} unless this
    argument is \code{NULL}. That is, row \code{i} of the output matrix will
    correspond to row \code{perm[i]} of the input matrix.

    The denominator will always be a divisor of the determinant of (some
    submatrix of) $A$, but is not guaranteed to be minimal or canonical in
    any other sense.

*******************************************************************************

    Hermite normal form

*******************************************************************************

void fmpz_mat_hnf(fmpz_mat_t H, const fmpz_mat_t A)

    Computes an integer matrix \code{H} such that \code{H} is the unique (row)
    Hermite normal form of \code{A}. The algorithm used is selected from the
    implementations in FLINT to be the one most likely to be optimal, based on
    the characteristics of the input matrix.

    Aliasing of \code{H} and \code{A} is allowed. The size of \code{H} must be
    the same as that of \code{A}.

void fmpz_mat_hnf_transform(fmpz_mat_t H, fmpz_mat_t U, const fmpz_mat_t A)

    Computes an integer matrix \code{H} such that \code{H} is the unique (row)
    Hermite normal form of \code{A} along with the transformation matrix
    \code{U} such that $UA = H$. The algorithm used is selected from the
    implementations in FLINT as per \code{fmpz_mat_hnf}.

    Aliasing of \code{H} and \code{A} is allowed. The size of \code{H} must be
    the same as that of \code{A} and \code{U} must be square of compatible 
    dimension (having the same number of rows as \code{A}).

void fmpz_mat_hnf_classical(fmpz_mat_t H, const fmpz_mat_t A)

    Computes an integer matrix \code{H} such that \code{H} is the unique (row)
    Hermite normal form of \code{A}. The algorithm used is straightforward and
    is described, for example, in \cite[Algorithm 2.4.4]{Coh1996}.

    Aliasing of \code{H} and \code{A} is allowed. The size of \code{H} must be
    the same as that of \code{A}.

void fmpz_mat_hnf_xgcd(fmpz_mat_t H, const fmpz_mat_t A)

    Computes an integer matrix \code{H} such that \code{H} is the unique (row)
    Hermite normal form of \code{A}. The algorithm used is an improvement on the
    basic algorithm and uses extended gcds to speed up computation, this method
    is described, for example, in \cite[Algorithm 2.4.5]{Coh1996}.

    Aliasing of \code{H} and \code{A} is allowed. The size of \code{H} must be
    the same as that of \code{A}.

void fmpz_mat_hnf_modular(fmpz_mat_t H, const fmpz_mat_t A, const fmpz_t D)

    Computes an integer matrix \code{H} such that \code{H} is the unique (row)
    Hermite normal form of the $m\times n$ matrix \code{A}, where \code{A} is
    assumed to be of rank $n$ and \code{D} is known to be a positive multiple of
    the determinant of the non-zero rows of \code{H}. The algorithm used here is
    due to Domich, Kannan and Trotter \cite{DomKanTro1987} and is also described
    in \cite[Algorithm 2.4.8]{Coh1996}.

    Aliasing of \code{H} and \code{A} is allowed. The size of \code{H} must be
    the same as that of \code{A}.

void fmpz_mat_hnf_minors(fmpz_mat_t H, const fmpz_mat_t A)

    Computes an integer matrix \code{H} such that \code{H} is the unique (row)
    Hermite normal form of the $m\times n$ matrix \code{A}, where \code{A} is
    assumed to be of rank $n$. The algorithm used here is due to Kannan and
    Bachem \cite{KanBac1979} and takes the principal minors to Hermite normal
    form in turn.

    Aliasing of \code{H} and \code{A} is allowed. The size of \code{H} must be
    the same as that of \code{A}.

void fmpz_mat_hnf_pernet_stein(fmpz_mat_t H, const fmpz_mat_t A,
                                                           flint_rand_t state)

    Computes an integer matrix \code{H} such that \code{H} is the unique (row)
    Hermite normal form of the $m\times n$ matrix \code{A}. The algorithm used
    here is due to Pernet and Stein \cite{PernetStein2010}.

    Aliasing of \code{H} and \code{A} is allowed. The size of \code{H} must be
    the same as that of \code{A}.

    The algorithm may fail to return the correct result with low probability,
    so \code{fmpz_mat_is_in_hnf} should be called afterwards to check the
    result. If the routine is called again with the same random state, each
    call gives an independent chance of computing the correct Hermite Normal
    Form.

int fmpz_mat_is_in_hnf(const fmpz_mat_t A)

    Checks that the given matrix is in Hermite normal form, returns 1 if so and
    0 otherwise.

*******************************************************************************

    Smith normal form

*******************************************************************************

void fmpz_mat_snf(fmpz_mat_t S, const fmpz_mat_t A)

    Computes an integer matrix \code{S} such that \code{S} is the unique Smith
    normal form of \code{A}. The algorithm used is selected from the
    implementations in FLINT to be the one most likely to be optimal, based on
    the characteristics of the input matrix.

    Aliasing of \code{S} and \code{A} is allowed. The size of \code{S} must be
    the same as that of \code{A}.

void fmpz_mat_snf_diagonal(fmpz_mat_t S, const fmpz_mat_t A)

    Computes an integer matrix \code{S} such that \code{S} is the unique Smith
    normal form of the diagonal matrix \code{A}. The algorithm used simply takes
    gcds of pairs on the diagonal in turn until the Smith form is obtained.

    Aliasing of \code{S} and \code{A} is allowed. The size of \code{S} must be
    the same as that of \code{A}.

void fmpz_mat_snf_kannan_bachem(fmpz_mat_t S, const fmpz_mat_t A)

    Computes an integer matrix \code{S} such that \code{S} is the unique Smith
    normal form of the diagonal matrix \code{A}. The algorithm used here is due
    to Kannan and Bachem \cite{KanBac1979} 

    Aliasing of \code{S} and \code{A} is allowed. The size of \code{S} must be
    the same as that of \code{A}.

void fmpz_mat_snf_iliopoulos(fmpz_mat_t S, const fmpz_mat_t A, const fmpz_t mod)

    Computes an integer matrix \code{S} such that \code{S} is the unique Smith
    normal form of the nonsingular $n\times n$ matrix \code{A}. The algorithm
    used is due to Iliopoulos \cite{Iliopoulos1989}.

    Aliasing of \code{S} and \code{A} is allowed. The size of \code{S} must be
    the same as that of \code{A}.

int fmpz_mat_is_in_snf(const fmpz_mat_t A)

    Checks that the given matrix is in Smith normal form, returns 1 if so and 0
    otherwise.

*******************************************************************************

    Special matrices

*******************************************************************************

void fmpz_mat_gram(fmpz_mat_t B, const fmpz_mat_t A)

    Sets \code{B} to the Gram matrix of the $m$-dimensional lattice \code{L} in 
    $n$-dimensional Euclidean space $R^n$ spanned by the rows of
    the $m x n$ matrix \code{A}. Dimensions must be compatible.
    \code{A} and \code{B} are allowed to be the same object if \code{A} is a 
    square matrix.

int fmpz_mat_is_hadamard(const fmpz_mat_t H)

    Returns nonzero iff $H$ is a Hadamard matrix, meaning
    that it is a square matrix, only has entries that are $\pm 1$,
    and satisfies $H^T = n H^{-1}$ where $n$ is the matrix size.

int fmpz_mat_hadamard(fmpz_mat_t H)

    Attempts to set the matrix $H$ to a Hadamard matrix, returning 1 if
    successful and 0 if unsuccessful.

    A Hadamard matrix of size $n$ can only exist if $n$ is 1, 2,
    or a multiple of 4. It is not known whether a
    Hadamard matrix exists for every size that is a multiple of 4.
    This function uses the Paley construction, which
    succeeds for all $n$ of the form $n = 2^e$ or $n = 2^e (q + 1)$ where
    $q$ is an odd prime power. Orders $n$ for which Hadamard matrices are
    known to exist but for which this construction fails are
    92, 116, 156, ... (OEIS A046116).
    
*******************************************************************************

    Conversions

*******************************************************************************

int fmpz_mat_get_d_mat(d_mat_t B, const fmpz_mat_t A)

    Sets the entries of \code{B} as doubles corresponding to the entries of
    \code{A}, rounding down towards zero if the latter cannot be represented
    exactly. The return value is -1 if any entry of \code{A} is too large to
    fit in the normal range of a double, and 0 otherwise.

int fmpz_mat_get_d_mat_transpose(d_mat_t B, const fmpz_mat_t A)

    Sets the entries of \code{B} as doubles corresponding to the entries of
    the transpose of \code{A}, rounding down towards zero if the latter cannot
    be represented exactly. The return value is -1 if any entry of \code{A} is
    too large to fit in the normal range of a double, and 0 otherwise.

void fmpz_mat_get_mpf_mat(mpf_mat_t B, const fmpz_mat_t A)

    Sets the entries of \code{B} as mpfs corresponding to the entries of
    \code{A}.

*******************************************************************************

    Cholesky Decomposition

*******************************************************************************

void fmpz_mat_chol_d(d_mat_t R, const fmpz_mat_t A)

    Computes \code{R}, the Cholesky factor of a symmetric, positive definite
    matrix \code{A} using the Cholesky decomposition process. (Sets \code{R}
    such that $A = RR^{T}$ where \code{R} is a lower triangular matrix.)

*******************************************************************************

    LLL

*******************************************************************************

int fmpz_mat_is_reduced(const fmpz_mat_t A, double delta, double eta)

    Returns a non-zero value if the basis \code{A} is LLL-reduced with factor
    (\code{delta}, \code{eta}), and otherwise returns zero. The function is
    mainly intended to be used for testing purposes in the \code{fmpz_lll}
    module.

int fmpz_mat_is_reduced_gram(const fmpz_mat_t A, double delta, double eta)

    Returns a non-zero value if the basis with Gram matrix \code{A} is
    LLL-reduced with factor (\code{delta}, \code{eta}), and otherwise returns
    zero. The function is mainly intended to be used for testing purposes in
    the \code{fmpz_lll} module.

int fmpz_mat_is_reduced_with_removal(const fmpz_mat_t A, double delta,
                                     double eta, const fmpz_t gs_B, int newd)

    Returns a non-zero value if the basis \code{A} is LLL-reduced with factor
    (\code{delta}, \code{eta}) and the squared Gram-Schmidt length of each
    $i$-th vector (where $i \ge$ \code{newd}) is greater than \code{gs_B}, and
    otherwise returns zero. The function is mainly intended to be used for
    testing purposes in the \code{fmpz_lll} module.

*******************************************************************************

    Classical LLL

*******************************************************************************

void fmpz_mat_lll_original(fmpz_mat_t A, const fmpq_t delta, const fmpq_t eta)

    Takes a basis $x_1, x_2, \ldots, x_m$ of the lattice $L \subset R^n$ (as
    the rows of a $m x n$ matrix \code{A}). The output is an (\code{delta},
    \code{eta})-reduced basis $y_1, y_2, \ldots, y_m$ of the lattice $L$ (as
    the rows of the same $m x n$ matrix \code{A}).

*******************************************************************************

    Modified LLL

*******************************************************************************

void fmpz_mat_lll_storjohann(fmpz_mat_t A, const fmpq_t delta,
                             const fmpq_t eta)

    Takes a basis $x_1, x_2, \ldots, x_m$ of the lattice $L \subset R^n$ (as
    the rows of a $m x n$ matrix \code{A}). The output is an (\code{delta},
    \code{eta})-reduced basis $y_1, y_2, \ldots, y_m$ of the lattice $L$ (as
    the rows of the same $m x n$ matrix \code{A}). Uses a modified version of
    LLL, which has better complexity in terms of the lattice dimension,
    introduced by Storjohann.

    See ``Faster Algorithms for Integer Lattice Basis Reduction.'' Technical 
    Report 249. Zurich, Switzerland: Department Informatik, ETH. July 30, 
    1996.