1 /*
2 Copyright (C) 2011 Fredrik Johansson
3 Copyright (C) 2012 Sebastian Pancratz
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <https://www.gnu.org/licenses/>.
11 */
12
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <gmp.h>
16 #include "flint.h"
17 #include "fmpz.h"
18 #include "fmpz_mat.h"
19 #include "ulong_extras.h"
20
21 int
main(void)22 main(void)
23 {
24 slong m, n, rep, i, j;
25 FLINT_TEST_INIT(state);
26
27 flint_printf("minpoly....");
28 fflush(stdout);
29
30 for (rep = 0; rep < 1000 * flint_test_multiplier(); rep++)
31 {
32 fmpz_t c;
33 fmpz_mat_t A;
34 fmpz_poly_t f, g, q, r;
35
36 m = n_randint(state, 4);
37 n = m;
38
39 fmpz_init(c);
40 fmpz_mat_init(A, m, n);
41 fmpz_poly_init(f);
42 fmpz_poly_init(g);
43 fmpz_poly_init(q);
44 fmpz_poly_init(r);
45
46 fmpz_mat_randtest(A, state, 10);
47
48 for (i = 0; i < n/2; i++)
49 {
50 for (j = 0; j < n/2; j++)
51 {
52 fmpz_zero(fmpz_mat_entry(A, i + n/2, j));
53 fmpz_zero(fmpz_mat_entry(A, i, j + n/2));
54 fmpz_set(fmpz_mat_entry(A, i + n/2, j + n/2), fmpz_mat_entry(A, i, j));
55 }
56 }
57
58 for (i = 0; i < 10; i++)
59 {
60 fmpz_randtest(c, state, 5);
61 fmpz_mat_similarity(A, n_randint(state, m), c);
62 }
63
64 fmpz_mat_minpoly(f, A);
65 fmpz_mat_charpoly(g, A);
66
67 fmpz_poly_divrem(q, r, g, f);
68
69 if (!fmpz_poly_is_zero(r))
70 {
71 flint_printf("FAIL: minpoly(A) doesn't divide charpoly(A).\n");
72 flint_printf("Matrix A:\n"), fmpz_mat_print(A), flint_printf("\n");
73 flint_printf("mp(A) = "), fmpz_poly_print_pretty(f, "X"), flint_printf("\n");
74 flint_printf("cp(A) = "), fmpz_poly_print_pretty(g, "X"), flint_printf("\n");
75 abort();
76 }
77
78 fmpz_clear(c);
79 fmpz_mat_clear(A);
80 fmpz_poly_clear(f);
81 fmpz_poly_clear(g);
82 fmpz_poly_clear(q);
83 fmpz_poly_clear(r);
84 }
85
86 for (rep = 0; rep < 1000 * flint_test_multiplier(); rep++)
87 {
88 fmpz_t c;
89 fmpz_mat_t A, B;
90 fmpz_poly_t f, g;
91
92 m = n_randint(state, 4);
93 n = m;
94
95 fmpz_init(c);
96 fmpz_mat_init(A, m, n);
97 fmpz_mat_init(B, m, n);
98 fmpz_poly_init(f);
99 fmpz_poly_init(g);
100
101 fmpz_mat_randtest(A, state, 10);
102
103 for (i = 0; i < n/2; i++)
104 {
105 for (j = 0; j < n/2; j++)
106 {
107 fmpz_zero(fmpz_mat_entry(A, i + n/2, j));
108 fmpz_zero(fmpz_mat_entry(A, i, j + n/2));
109 fmpz_set(fmpz_mat_entry(A, i + n/2, j + n/2), fmpz_mat_entry(A, i, j));
110 }
111 }
112
113 fmpz_mat_set(B, A);
114
115 for (i = 0; i < 10; i++)
116 {
117 fmpz_randtest(c, state, 5);
118 fmpz_mat_similarity(B, n_randint(state, m), c);
119 }
120
121 fmpz_mat_minpoly(f, A);
122 fmpz_mat_minpoly(g, B);
123
124 if (!fmpz_poly_equal(f, g))
125 {
126 flint_printf("FAIL: minpoly(A) != minpoly(P^{-1}AP).\n");
127 flint_printf("Matrix A:\n"), fmpz_mat_print(A), flint_printf("\n");
128 flint_printf("Matrix P^{-1}AP:\n"), fmpz_mat_print(B), flint_printf("\n");
129 flint_printf("mp(A) = "), fmpz_poly_print_pretty(f, "X"), flint_printf("\n");
130 flint_printf("mp(P^{-1}AP) = "), fmpz_poly_print_pretty(g, "X"), flint_printf("\n");
131 abort();
132 }
133
134 fmpz_clear(c);
135 fmpz_mat_clear(A);
136 fmpz_mat_clear(B);
137 fmpz_poly_clear(f);
138 fmpz_poly_clear(g);
139 }
140
141 FLINT_TEST_CLEANUP(state);
142
143 flint_printf("PASS\n");
144 return 0;
145 }
146