Make matrix::solve() work with non-normal zeros.
[ginac.git] / check / exam_matrices.cpp
1
2 /** @file exam_matrices.cpp
3  *
4  *  Here we examine manipulations on GiNaC's symbolic matrices. */
5
6 /*
7  *  GiNaC Copyright (C) 1999-2018 Johannes Gutenberg University Mainz, Germany
8  *
9  *  This program is free software; you can redistribute it and/or modify
10  *  it under the terms of the GNU General Public License as published by
11  *  the Free Software Foundation; either version 2 of the License, or
12  *  (at your option) any later version.
13  *
14  *  This program is distributed in the hope that it will be useful,
15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  *  GNU General Public License for more details.
18  *
19  *  You should have received a copy of the GNU General Public License
20  *  along with this program; if not, write to the Free Software
21  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
22  */
23
24 #include "ginac.h"
25 using namespace GiNaC;
26
27 #include <iostream>
28 #include <stdexcept>
29 using namespace std;
30
31 static unsigned matrix_determinants()
32 {
33         unsigned result = 0;
34         ex det;
35         matrix m1(1,1), m2(2,2), m3(3,3), m4(4,4);
36         symbol a("a"), b("b"), c("c");
37         symbol d("d"), e("e"), f("f");
38         symbol g("g"), h("h"), i("i");
39         
40         // check symbolic trivial matrix determinant
41         m1 = matrix{{a}};
42         det = m1.determinant();
43         if (det != a) {
44                 clog << "determinant of 1x1 matrix " << m1
45                      << " erroneously returned " << det << endl;
46                 ++result;
47         }
48         
49         // check generic dense symbolic 2x2 matrix determinant
50         m2 = matrix{{a, b},
51                     {c, d}};
52         det = m2.determinant();
53         if (det != (a*d-b*c)) {
54                 clog << "determinant of 2x2 matrix " << m2
55                      << " erroneously returned " << det << endl;
56                 ++result;
57         }
58         
59         // check generic dense symbolic 3x3 matrix determinant
60         m3 = matrix{{a, b, c},
61                     {d, e, f},
62                     {g, h, i}};
63         det = m3.determinant();
64         if (det != (a*e*i - a*f*h - d*b*i + d*c*h + g*b*f - g*c*e)) {
65                 clog << "determinant of 3x3 matrix " << m3
66                      << " erroneously returned " << det << endl;
67                 ++result;
68         }
69         
70         // check dense numeric 3x3 matrix determinant
71         m3 = matrix{{0, -1,  3},
72                     {3, -2,  2},
73                     {3,  4, -2}};
74         det = m3.determinant();
75         if (det != 42) {
76                 clog << "determinant of 3x3 matrix " << m3
77                      << " erroneously returned " << det << endl;
78                 ++result;
79         }
80         
81         // check dense symbolic 2x2 matrix determinant
82         m2 = matrix{{a/(a-b), 1},
83                     {b/(a-b), 1}};
84         det = m2.determinant();
85         if (det != 1) {
86                 if (det.normal() == 1)  // only half wrong
87                         clog << "determinant of 2x2 matrix " << m2
88                              << " was returned unnormalized as " << det << endl;
89                 else  // totally wrong
90                         clog << "determinant of 2x2 matrix " << m2
91                              << " erroneously returned " << det << endl;
92                 ++result;
93         }
94         
95         // check sparse symbolic 4x4 matrix determinant
96         m4.set(0,1,a).set(1,0,b).set(3,2,c).set(2,3,d);
97         det = m4.determinant();
98         if (det != a*b*c*d) {
99                 clog << "determinant of 4x4 matrix " << m4
100                      << " erroneously returned " << det << endl;
101                 ++result;
102         }
103         
104         // check characteristic polynomial
105         m3 = matrix{{a, -2,   2},
106                     {3, a-1,  2},
107                     {3,  4,  a-3}};
108         ex p = m3.charpoly(a);
109         if (p != 0) {
110                 clog << "charpoly of 3x3 matrix " << m3
111                      << " erroneously returned " << p << endl;
112                 ++result;
113         }
114         
115         return result;
116 }
117
118 static unsigned matrix_invert1()
119 {
120         unsigned result = 0;
121         matrix m(1,1);
122         symbol a("a");
123         
124         m.set(0,0,a);
125         matrix m_i = m.inverse();
126         
127         if (m_i(0,0) != pow(a,-1)) {
128                 clog << "inversion of 1x1 matrix " << m
129                      << " erroneously returned " << m_i << endl;
130                 ++result;
131         }
132         
133         return result;
134 }
135
136 static unsigned matrix_invert2()
137 {
138         unsigned result = 0;
139         symbol a("a"), b("b"), c("c"), d("d");
140         matrix m = {{a, b},
141                     {c, d}};
142         matrix m_i = m.inverse();
143         ex det = m.determinant();
144         
145         if ((normal(m_i(0,0)*det) != d) ||
146             (normal(m_i(0,1)*det) != -b) ||
147             (normal(m_i(1,0)*det) != -c) ||
148             (normal(m_i(1,1)*det) != a)) {
149                 clog << "inversion of 2x2 matrix " << m
150                      << " erroneously returned " << m_i << endl;
151                 ++result;
152         }
153         
154         return result;
155 }
156
157 static unsigned matrix_invert3()
158 {
159         unsigned result = 0;
160         symbol a("a"), b("b"), c("c");
161         symbol d("d"), e("e"), f("f");
162         symbol g("g"), h("h"), i("i");
163         matrix m = {{a, b, c},
164                     {d, e, f},
165                     {g, h, i}};
166         matrix m_i = m.inverse();
167         ex det = m.determinant();
168         
169         if ((normal(m_i(0,0)*det) != (e*i-f*h)) ||
170             (normal(m_i(0,1)*det) != (c*h-b*i)) ||
171             (normal(m_i(0,2)*det) != (b*f-c*e)) ||
172             (normal(m_i(1,0)*det) != (f*g-d*i)) ||
173             (normal(m_i(1,1)*det) != (a*i-c*g)) ||
174             (normal(m_i(1,2)*det) != (c*d-a*f)) ||
175             (normal(m_i(2,0)*det) != (d*h-e*g)) ||
176             (normal(m_i(2,1)*det) != (b*g-a*h)) ||
177             (normal(m_i(2,2)*det) != (a*e-b*d))) {
178                 clog << "inversion of 3x3 matrix " << m
179                      << " erroneously returned " << m_i << endl;
180                 ++result;
181         }
182         
183         return result;
184 }
185
186 static unsigned matrix_solve2()
187 {
188         // check the solution of the multiple system A*X = B:
189         //       [ 1  2 -1 ] [ x0 y0 ]   [ 4 0 ]
190         //       [ 1  4 -2 ]*[ x1 y1 ] = [ 7 0 ]
191         //       [ a -2  2 ] [ x2 y2 ]   [ a 4 ]
192         unsigned result = 0;
193         symbol a("a");
194         symbol x0("x0"), x1("x1"), x2("x2");
195         symbol y0("y0"), y1("y1"), y2("y2");
196         matrix A = {{1,  2, -1},
197                     {1,  4, -2},
198                     {a, -2,  2}};
199         matrix B = {{4, 0},
200                     {7, 0},
201                     {a, 4}};
202         matrix X = {{x0 ,y0},
203                     {x1, y1},
204                     {x2, y2}};
205         matrix cmp = {{1, 0},
206                       {3, 2},
207                       {3, 4}};
208         matrix sol(A.solve(X, B));
209         if (cmp != sol) {
210                 clog << "Solving " << A << " * " << X << " == " << B << endl
211                      << "erroneously returned " << sol << endl;
212                 result = 1;
213         }
214
215         return result;
216 }
217
218 static unsigned matrix_evalm()
219 {
220         unsigned result = 0;
221
222         matrix S {{1, 2},
223                   {3, 4}};
224         matrix T {{1, 1},
225                   {2, -1}};
226         matrix R {{27, 14},
227                   {36, 26}};
228
229         ex e = ((S + T) * (S + 2*T));
230         ex f = e.evalm();
231         if (!f.is_equal(R)) {
232                 clog << "Evaluating " << e << " erroneously returned " << f << " instead of " << R << endl;
233                 result++;
234         }
235
236         return result;
237 }
238
239 static unsigned matrix_rank()
240 {
241         unsigned result = 0;
242         symbol x("x"), y("y");
243         matrix m(3,3);
244
245         // the zero matrix always has rank 0
246         if (m.rank() != 0) {
247                 clog << "The rank of " << m << " was not computed correctly." << endl;
248                 ++result;
249         }
250
251         // a trivial rank one example
252         m = {{1, 0, 0},
253              {2, 0, 0},
254              {3, 0, 0}};
255         if (m.rank() != 1) {
256                 clog << "The rank of " << m << " was not computed correctly." << endl;
257                 ++result;
258         }
259
260         // an example from Maple's help with rank two
261         m = {{x,   1,  0},
262              {0,   0,  1},
263              {x*y, y,  1}};
264         if (m.rank() != 2) {
265                 clog << "The rank of " << m << " was not computed correctly." << endl;
266                 ++result;
267         }
268
269         // the 3x3 unit matrix has rank 3
270         m = ex_to<matrix>(unit_matrix(3,3));
271         if (m.rank() != 3) {
272                 clog << "The rank of " << m << " was not computed correctly." << endl;
273                 ++result;
274         }
275
276         return result;  
277 }
278
279 unsigned matrix_solve_nonnormal()
280 {
281         symbol a("a"), b("b"), c("c"), x("x");
282         // This matrix has a non-normal zero element!
283         matrix mx {{1,0,0},
284                    {0,1/(x+1)-(x-1)/(x*x-1),1},
285                    {0,0,0}};
286         matrix zero {{0}, {0}, {0}};
287         matrix vars {{a}, {b}, {c}};
288         try {
289                 matrix sol_gauss   = mx.solve(vars, zero, solve_algo::gauss);
290                 matrix sol_divfree = mx.solve(vars, zero, solve_algo::divfree);
291                 matrix sol_bareiss = mx.solve(vars, zero, solve_algo::bareiss);
292                 if (sol_gauss != sol_divfree  ||  sol_gauss != sol_bareiss) {
293                         clog << "different solutions while solving "
294                              << mx << " * " << vars << " == " << zero << endl
295                              << "gauss:   " << sol_gauss << endl
296                              << "divfree: " << sol_divfree << endl
297                              << "bareiss: " << sol_bareiss << endl;
298                         return 1;
299                 }
300         } catch (const exception & e) {
301                 clog << "exception thrown while solving "
302                      << mx << " * " << vars << " == " << zero << endl;
303                 return 1;
304         }
305         return 0;
306 }
307
308 static unsigned matrix_misc()
309 {
310         unsigned result = 0;
311         symbol a("a"), b("b"), c("c"), d("d"), e("e"), f("f");
312         matrix m1 = {{a, b},
313                      {c, d}};
314         ex tr = trace(m1);
315         
316         // check a simple trace
317         if (tr.compare(a+d)) {
318                 clog << "trace of 2x2 matrix " << m1
319                      << " erroneously returned " << tr << endl;
320                 ++result;
321         }
322         
323         // and two simple transpositions
324         matrix m2 = transpose(m1);
325         if (m2(0,0) != a || m2(0,1) != c || m2(1,0) != b || m2(1,1) != d) {
326                 clog << "transpose of 2x2 matrix " << m1
327                          << " erroneously returned " << m2 << endl;
328                 ++result;
329         }
330         matrix m3 = {{a, b},
331                      {c, d},
332                      {e, f}};
333         if (transpose(transpose(m3)) != m3) {
334                 clog << "transposing 3x2 matrix " << m3 << " twice"
335                      << " erroneously returned " << transpose(transpose(m3)) << endl;
336                 ++result;
337         }
338         
339         // produce a runtime-error by inverting a singular matrix and catch it
340         matrix m4(2,2);
341         matrix m5;
342         bool caught = false;
343         try {
344                 m5 = inverse(m4);
345         } catch (std::runtime_error err) {
346                 caught = true;
347         }
348         if (!caught) {
349                 cerr << "singular 2x2 matrix " << m4
350                      << " erroneously inverted to " << m5 << endl;
351                 ++result;
352         }
353         
354         return result;
355 }
356
357 unsigned exam_matrices()
358 {
359         unsigned result = 0;
360         
361         cout << "examining symbolic matrix manipulations" << flush;
362         
363         result += matrix_determinants();  cout << '.' << flush;
364         result += matrix_invert1();  cout << '.' << flush;
365         result += matrix_invert2();  cout << '.' << flush;
366         result += matrix_invert3();  cout << '.' << flush;
367         result += matrix_solve2();  cout << '.' << flush;
368         result += matrix_evalm();  cout << "." << flush;
369         result += matrix_rank();  cout << "." << flush;
370         result += matrix_solve_nonnormal();  cout << "." << flush;
371         result += matrix_misc();  cout << '.' << flush;
372         
373         return result;
374 }
375
376 int main(int argc, char** argv)
377 {
378         return exam_matrices();
379 }