Debian Codegraph @

3rdparty/dissection/src/Driver/C_KernDetect.cpp

raw
1 /*! \file C_KernDetect.cpp
2 \brief Kernel detection algorithm : symm <= DOI: 10.1002/nme.4729 / unsymm
3 \author Atsushi. Suzuki, Laboratoire Jacques-Louis Lions
4 \date Jun. 20th 2014
5 \date Jul. 12th 2015
6 \date Nov. 30th 2016
7 */
8
9 // This file is part of Dissection
10 //
11 // Dissection is free software: you can redistribute it and/or modify
12 // it under the terms of the GNU General Public License as published by
13 // the Free Software Foundation, either version 3 of the License, or
14 // (at your option) any later version.
15 //
16 // Linking Dissection statically or dynamically with other modules is making
17 // a combined work based on Disssection. Thus, the terms and conditions of
18 // the GNU General Public License cover the whole combination.
19 //
20 // As a special exception, the copyright holders of Dissection give you
21 // permission to combine Dissection program with free software programs or
22 // libraries that are released under the GNU LGPL and with independent modules
23 // that communicate with Dissection solely through the Dissection-fortran
24 // interface. You may copy and distribute such a system following the terms of
25 // the GNU GPL for Dissection and the licenses of the other code concerned,
26 // provided that you include the source code of that other code when and as
27 // the GNU GPL requires distribution of source code and provided that you do
28 // not modify the Dissection-fortran interface.
29 //
30 // Note that people who make modified versions of Dissection are not obligated
31 // to grant this special exception for their modified versions; it is their
32 // choice whether to do so. The GNU General Public License gives permission to
33 // release a modified version without this exception; this exception also makes
34 // it possible to release a modified version which carries forward this
35 // exception. If you modify the Dissection-fortran interface, this exception
36 // does not apply to your modified version of Dissection, and you must remove
37 // this exception when you distribute your modified version.
38 //
39 // This exception is an additional permission under section 7 of the GNU
40 // General Public License, version 3 ("GPLv3")
41 //
42 // Dissection is distributed in the hope that it will be useful,
43 // but WITHOUT ANY WARRANTY; without even the implied warranty of
44 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
45 // GNU General Public License for more details.
46 //
47 // You should have received a copy of the GNU General Public License
48 // along with Dissection. If not, see <http://www.gnu.org/licenses/>.
49 //
50
51 #include "Compiler/OptionLibrary.hpp"
52 #include "Driver/C_KernDetect.hpp"
53 #include "Algebra/ColumnMatrix.hpp"
54 #include "Algebra/VectorArray.hpp"
55 #include "Compiler/DissectionIO.hpp"
56
57 // T may be std::complex of U and W is in higher precision than T
58 template<typename T, typename U, typename W, typename Y>
59 bool check_kern(const int n0, const int lda, const int n, W *a_ini,
60 int *permute,
61 const int dim_augkern, const U &eps,
62 const U &eps_param, const bool flag_sym, U *errors,
63 const bool verbose, FILE *fp)
64 {
65 bool flag;
66 // W *a_q, *a_fq, *proj, *nsp, *nsp2;
67 // W *v, *alpha;
68 const W zero(0.0);
69 const W one(1.0);
70 const W none(-1.0);
71 const U Uzero(0.0);
72
73 ColumnMatrix<W> a_q(n, n);
74 ColumnMatrix<W> a_fq(n, n);
75 ColumnMatrix<W> proj(n, n);
76 ColumnMatrix<W> nsp(n, n);
77 ColumnMatrix<W> nsp2(n,n);
78 VectorArray<W> v(n);
79 VectorArray<W> alpha(n);
80
81 for (int j = 0; j < n; j++) {
82 for (int i = 0; i < n; i++) {
83 const int ij = permute[i] + permute[j] * lda;
84 a_fq(i, j) = a_ini[ij];
85 }
86 }
87 // duplicate of a_fq
88 a_q.copy(a_fq);
89 if (flag_sym) {
90 full_ldlt<W>(n, a_fq.addrCoefs(), n);
91 }
92 else {
93 full_ldu<W>(n, a_fq.addrCoefs(), n);
94 }
95 int n1 = n - n0;
96 for (int j = 0; j < n0; j++) {
97 for (int i = 0; i < n1; i++) {
98 nsp(i, j) = a_q(i, (j + n1)); // nsp[i + j * n] = a_q[i + (j + n1) * n];
99
100 }
101 for (int i = n1; i < n; i++) {
102 nsp(i, j) = zero; // nsp[i + j * n] = zero;
103 }
104 nsp((n1 + j), j) = none;
105 }
106 full_fwbw_perturb_multi<W, U>(n1, n0, a_q.addrCoefs(), n,
107 a_fq.addrCoefs(), nsp.addrCoefs(), dim_augkern,
108 eps,
109 flag_sym);
110 // compute projection matrix
111 for (int i = 0; i < n0; i++) {
112 for (int j = 0; j <= i; j++) {
113 proj(i, j) = blas_dot<W>(n,
114 nsp.addrCoefs() + (i * n), 1,
115 nsp.addrCoefs() + (j * n), 1); // lower
116 proj(j, i) = blas_conj(proj(i, j)); // upper
117 }
118 }
119 // Hermite symmteric with complex inner product
120 full_ldlh<W>(n0, proj.addrCoefs(), n);
121 for (int m = (n0 - 1); m <= (n0 + 1); m++) {
122 int k = n - m;
123 U res_err = U(0.0);
124 for (int j = 0; j < n; j++) {
125 for (int i = 0; i < k; i++) {
126 nsp2(i, j) = a_q(i, j); // nsp2[i + j * n] = a_q[i + j * n];
127 }
128 }
129 full_fwbw_perturb_multi<W, U>(k, n, a_q.addrCoefs(), n,
130 a_fq.addrCoefs(), nsp2.addrCoefs(),
131 dim_augkern,
132 eps,
133 flag_sym);
134 for (int j = 0; j < n; j++) {
135 for (int i = k; i < n; i++) {
136 nsp2(i, j) = zero; // nsp2[i + j * n] = zero;
137 }
138 nsp2(j, j) -= one; // nsp2[j + j * n] -= one;
139 }
140 for (int j = 0; j < k; j++) {
141 for (int i = 0; i < n; i++) {
142 v[i] = nsp2(i, j); // v[i] = nsp2[i + j * n];
143 }
144 U res = conv_prec<U, Y>(blas_l2norm<W, Y>(n, v.addrCoefs(), 1));
145 res_err = res_err > res ? res_err : res;
146 }
147 for (int j = k; j < n; j++) {
148 for (int i = 0; i < n; i++) {
149 v[i] = nsp2(i, j); // v[i] = nsp2[i + j * n];
150 }
151 // alpha = 1; beta = 0;
152 blas_gemv<W>(CblasTrans, n, n0, one,
153 nsp.addrCoefs(), n, v.addrCoefs(), 1,
154 zero, alpha.addrCoefs(), 1);
155 full_fwbw_part<W>(n0, proj.addrCoefs(), n, alpha.addrCoefs());
156 // alpha = -1; beta = 1;
157 blas_gemv<W>(CblasNoTrans, n, n0, none,
158 nsp.addrCoefs(), n, alpha.addrCoefs(), 1,
159 one, v.addrCoefs(), 1);
160 U res = conv_prec<U, Y>(blas_l2norm<W, Y>(n, v.addrCoefs(), 1));
161 res_err = res_err > res ? res_err : res;
162 }
163 errors[m - n0 + 1] = res_err;
164 }
165 flag = false;
166 if ((errors[0] > eps_param) && (errors[1] < eps_param) &&
167 (errors[2] > eps_param)) {
168 flag = true;
169 }
170
171 return flag;
172 }
173
174 template
175 bool check_kern<double, double,
176 quadruple, quadruple>(const int n0, const int lda, const int n,
177 quadruple *a_ini, int *permute,
178 const int dim_augkern, const double &eps,
179 const double &eps_param,
180 const bool flag_sym,
181 double *errors,
182 const bool verbose, FILE *fp);
183 template
184 bool check_kern<complex<double>,
185 double,
186 complex<quadruple>,
187 quadruple>(const int n0,
188 const int lda,
189 const int n,
190 complex<quadruple> *a_ini,
191 int *permute,
192 const int dim_augkern,
193 const double &eps,
194 const double &eps_param,
195 const bool flag_sym,
196 double *errors,
197 const bool verbose, FILE *fp);
198
199 #ifndef NO_OCTRUPLE
200 template
201 bool check_kern<quadruple, quadruple,
202 octruple, octruple>(const int n0, const int lda,
203 const int n,
204 octruple *a_ini, int *permute,
205 const int dim_augkern,
206 const quadruple &eps,
207 const quadruple &eps_param,
208 const bool flag_sym,
209 quadruple *errors,
210 const bool verbose, FILE *fp);
211 template
212 bool
213 check_kern<complex<quadruple>,
214 quadruple,
215 complex<octruple>,
216 octruple>(const int n0,
217 const int lda,
218 const int n,
219 complex<octruple> *a_ini,
220 int *permute,
221 const int dim_augkern,
222 const quadruple &eps,
223 const quadruple &eps_param,
224 const bool flag_sym,
225 quadruple *errors,
226 const bool verbose, FILE *fp);
227 #endif
228 //
229 // T may be std::complex of U and W is in higher precision than T
230 template<typename T, typename U, typename W, typename Y>
231 U check_matrixerr(const int lda, const int n,
232 W *a,
233 const int dim_augkern, const int k,
234 int *permute,
235 const U &eps,
236 const bool flag_sym)
237
238 {
239 U error;
240 const U Uzero(0.0);
241 const W one(1.0);
242 ColumnMatrix<W> nsp2(n, n);
243 ColumnMatrix<W> nsp3(n, n);
244 ColumnMatrix<W> nsp4(n, n);
245 VectorArray<W> v(n);
246
247 for (int i = 0; i < (n * n); i++) {
248 nsp2.addrCoefs()[i] = one;
249 }
250 // permutation is given
251 for (int j = 0; j < k; j++) {
252 for (int i = 0; i < k; i++) {
253 const int ij0 = permute[i] + permute[j] * lda;
254 nsp2(i, j) = W(a[ij0]); // const int ij1 = i + j * n;
255 }
256 }
257 nsp3.copy(nsp2);
258 nsp4.copy(nsp2);
259 if (flag_sym) {
260 full_ldlt<W>(k, nsp3.addrCoefs(), n); // factorization is done in
261 } // higher accurary
262 else {
263 full_ldu<W>(k, nsp3.addrCoefs(), n);
264 }
265 full_fwbw_perturb_multi<W, U>(k, k,
266 nsp4.addrCoefs(), n,
267 nsp3.addrCoefs(), nsp2.addrCoefs(),
268 dim_augkern, eps,
269 flag_sym);
270 for (int i = 0; i < k; i++) {
271 nsp2(i, i) -= one; // nsp2[i + i * n] -= one;
272 }
273 error = matrix_infty_norm<W, U>(k, nsp2.addrCoefs(), n);
274
275 return error;
276 }
277
278 template
279 double check_matrixerr<double, double,
280 quadruple, quadruple>(const int lda, const int n,
281 quadruple *a,
282 const int dim_augkern,
283 const int k, int *permute,
284 const double &eps,
285 const bool flag_sym);
286
287 template
288 double check_matrixerr<complex<double>,
289 double,
290 complex<quadruple>,
291 quadruple>(const int lda,
292 const int n,
293 complex<quadruple> *a,
294 const int dim_augkern,
295 const int k,
296 int *permute,
297 const double &eps,
298 const bool flag_sym);
299 #ifndef NO_OCTRUPLE
300 template
301 quadruple check_matrixerr<quadruple,
302 quadruple,
303 octruple,
304 octruple>(const int lda, const int n,
305 octruple *a,
306 const int dim_augkern,
307 const int k, int *permute,
308 const quadruple &eps,
309 const bool flag_sym);
310
311 template
312 quadruple
313 check_matrixerr<complex<quadruple>,
314 quadruple,
315 complex<octruple>,
316 octruple>(const int lda,
317 const int n,
318 complex<octruple> *a,
319 const int dim_augkern,
320 const int k,
321 int *permute,
322 const quadruple &eps,
323 const bool flag_sym);
324 #endif
325 //
326
327 template<typename T, typename U>
328 void verify_kernels(const int n0, const int n, const T *a_ini,
329 const T *a_fact, const int lda,
330 const double eps, U *errors,
331 const bool verbose, FILE *fp)
332 {
333 const T one(1.0);
334 const T zero(0.0);
335 const T none(-1.0);
336
337 ColumnMatrix<T> a_p(n, n);
338 const int n1 = n - n0;
339
340 for (int i = 0; i < n; i++) {
341 for (int j = 0; j < n ; j++) {
342 // const int ij0 = permute[i] + permute[j] * n;
343 const int ij0 = i + j * lda;
344 a_p(i, j) = a_ini[ij0]; // const int ij1 = i + j * n;
345 }
346 }
347 // compute [A_11^-1 A_12]
348 // [ -I ]
349 VectorArray<T> v(n);
350 VectorArray<T> w(n);
351 for (int j = n1; j < n; j++) {
352 for (int i = 0; i < n1; i++) {
353 // const int ij0 = permute[i] + permute[j] * n;
354 const int ij0 = i + j * lda;
355 v[i] = a_ini[ij0];
356 }
357 full_fwbw_part<T>(n1, (T *)a_fact, lda, v.addrCoefs()); //cast : 22 May 2018
358 for (int i = n1; i < n; i++) {
359 v[i] = zero;
360 }
361 v[j] = none;
362 blas_gemv<T>(CblasNoTrans, n, n, one, a_p.addrCoefs(), n,
363 v.addrCoefs(), 1, zero,
364 w.addrCoefs(), 1);
365 #if 0
366 diss_printf(verbose, fp, "%s %d verify_kernels %d\n",
367 __FILE__, __LINE__, n);
368 for (int i = 0; i < n; i++) {
369 diss_printf(verbose, fp, "%d %s %s\n", i, tostring<T>(v[i]).c_str(),
370 tostring<T>(w[i]).c_str());
371 }
372 #endif
373 errors[j - n1] = blas_l2norm<T, U>(n, w.addrCoefs(), 1);
374 }
375 }
376
377 template
378 void verify_kernels<double, double>(const int n0, const int n,
379 const double *a_ini,
380 const double *a_fact,
381 const int lda,
382 const double eps,
383 double *errors,
384 const bool verbose, FILE *fp);
385
386 template
387 void verify_kernels<complex<double>, double>(const int n0, const int n,
388 const complex<double> *a_ini,
389 const complex<double> *a_fact,
390 const int lda,
391 const double eps,
392 double *errors,
393 const bool verbose, FILE *fp);
394 template
395 void verify_kernels<quadruple, quadruple>(const int n0, const int n,
396 const quadruple *a_ini,
397 const quadruple *a_fact,
398 const int lda,
399 const double eps,
400 quadruple *errors,
401 const bool verbose, FILE *fp);
402
403 template
404 void verify_kernels<complex<quadruple>,
405 quadruple>(const int n0, const int n,
406 const complex<quadruple> *a_ini,
407 const complex<quadruple> *a_fact,
408 const int lda,
409 const double eps,
410 quadruple *errors,
411 const bool verbose, FILE *fp);
412 //
413
414 template<typename T, typename U>
415 void HouseholderVector_complex(int n, T *x, T *v, T *gamma)
416 {
417 const U zero(0.0);
418 const U one(1.0);
419 const U two(2.0);
420 const U onehalf(1.5);
421
422 const T czero(zero, zero);
423 const T cone(one, zero);
424 const T ctwo(two, zero);
425 const U pi(M_PI);
426 U s = blas_l2norm2<T, U>((n - 1), &x[1], 1);
427
428 v[0] = cone;
429 for (int i = 1; i < n; i++) {
430 v[i] = x[i];
431 }
432 if (s == zero) {
433 *gamma = czero;
434 }
435 else {
436 // U x0arg = std::arg(x[0]);
437 U x0arg = atan2(x[0].imag(), x[0].real());
438 const T alpha = complex<U>(cos(x0arg), sin(x0arg));
439 U xabs = sqrt<U>(x[0].real() * x[0].real() +
440 x[0].imag() * x[0].imag());
441
442 if ((x0arg >= pi / two) && (x0arg < pi * onehalf)) {
443 v[0] = alpha * (xabs + sqrt<U>(s));
444 }
445 else {
446 v[0] = alpha * (-s) / (xabs + sqrt<U>(s));
447 }
448 const U v0r(v[0].real());
449 const U v0i(v[0].imag());
450 const U v0sq = v0r * v0r + v0i * v0i;
451 *gamma = ctwo * v0sq / (s + v0sq);
452 T z = one / v[0];
453 for (int i = 0; i < n; i++) {
454 v[i] *= z;
455 }
456 }
457 }
458
459 template
460 void HouseholderVector_complex<complex<double>, double>(int n,
461 complex<double> *x,
462 complex<double> *v,
463 complex<double> *gamma);
464
465 template
466 void HouseholderVector_complex<complex<quadruple>,
467 quadruple>(int n,
468 complex<quadruple> *x,
469 complex<quadruple> *v,
470 complex<quadruple> *gamma);
471
472 template
473 void HouseholderVector_complex<complex<float>, float>(int n,
474 complex<float> *x,
475 complex<float> *v,
476 complex<float> *gamma);
477
478 //
479
480 template<typename T>
481 void HouseholderVector(int n, T *x, T *v, T *gamma)
482 {
483 const T one(1.0);
484 const T zero(0.0);
485 const T two(2.0);
486 const T s = blas_l2norm2<T, T>((n - 1), &x[1], 1);
487 v[0] = one;
488 for (int i = 1; i < n; i++) {
489 v[i] = x[i];
490 }
491 if (s == zero) {
492 *gamma = zero;
493 }
494 else {
495 T z = sqrt<T>(x[0] * x[0] + s);
496 if (x[0] <= zero) {
497 v[0] = x[0] - z;
498 }
499 else {
500 v[0] = (-s) / (x[0] + z);
501 }
502 *gamma = two * v[0] * v[0] / (s + v[0] * v[0]);
503 z = one / v[0];
504 for (int i = 0; i < n; i++) {
505 v[i] *= z;
506 }
507 }
508 }
509
510 template<>
511 void HouseholderVector<complex<double> >(int n,
512 complex<double> *x,
513 complex<double> *v,
514 complex<double> *gamma)
515 {
516 HouseholderVector_complex<complex<double>, double>(n, x, v, gamma);
517 }
518
519 template<>
520 void HouseholderVector<complex<quadruple> >(int n,
521 complex<quadruple> *x,
522 complex<quadruple> *v,
523 complex<quadruple> *gamma)
524 {
525 HouseholderVector_complex<complex<quadruple>, quadruple>(n, x, v, gamma);
526 }
527
528 template<>
529 void HouseholderVector<complex<octruple> >(int n,
530 complex<octruple> *x,
531 complex<octruple> *v,
532 complex<octruple> *gamma)
533 {
534 HouseholderVector_complex<complex<octruple>, octruple>(n, x, v, gamma);
535 }
536
537 template<>
538 void HouseholderVector<complex<float> >(int n,
539 complex<float> *x,
540 complex<float> *v,
541 complex<float> *gamma)
542 {
543 HouseholderVector_complex<complex<float>, float>(n, x, v, gamma);
544 }
545
546
547 template
548 void HouseholderVector<double>(int n, double *x, double *v, double *gamma);
549
550 template
551 void HouseholderVector<quadruple>(int n, quadruple *x, quadruple *v,
552 quadruple *gamma);
553
554 template
555 void HouseholderVector<float>(int n, float *x, float *v, float *gamma);
556
557 #if 0
558 template
559 void HouseholderVector<complex<double> >(int n,
560 complex<double> *x,
561 complex<double> *v,
562 complex<double> *gamma);
563
564 template
565 void HouseholderVector<complex<quadruple> >(int n,
566 complex<quadruple> *x,
567 complex<quadruple> *v,
568 complex<quadruple> *gamma);
569 #endif
570 //
571
572 template<typename T>
573 void HouseholderReflection(int n, T *a, int lda, T *v, T *w, const T &gamma)
574 {
575 const T one(1.0);
576 const T zero(0.0);
577 blas_gemv<T>(CblasConjTrans, n, n, one, a, lda, v, 1, zero, w, 1);
578 T ngamma = (-gamma);
579 blas_gerc<T>(n, n, ngamma, v, 1, w, 1, a, lda);
580 }
581
582 template
583 void HouseholderReflection<double>(int n, double *a, int lda, double *v,
584 double *w, const double &gamma);
585
586 template
587 void HouseholderReflection<complex<double> >(int n, complex<double> *a, int lda,
588 complex<double> *v,
589 complex<double> *w,
590 const complex<double> &gamma);
591
592 template
593 void HouseholderReflection<quadruple>(int n, quadruple *a, int lda,
594 quadruple *v,
595 quadruple *w, const quadruple &gamma);
596
597 template
598 void
599 HouseholderReflection<complex<quadruple> >(int n,
600 complex<quadruple> *a, int lda,
601 complex<quadruple> *v,
602 complex<quadruple> *w,
603 const complex<quadruple> &gamma);
604 template
605 void HouseholderReflection<float>(int n, float *a, int lda, float *v,
606 float *w, const float &gamma);
607
608 template
609 void HouseholderReflection<complex<float> >(int n, complex<float> *a, int lda,
610 complex<float> *v,
611 complex<float> *w,
612 const complex<float> &gamma);
613
614 //
615
616 // T may be complex of U
617 template<typename T, typename U>
618 int hqr_pivot(const int n, T *a, int *permute)
619 {
620 const T Tzero(0.0);
621 const U Uzero(0.0);
622 int n0, k;
623
624 VectorArray<U> cc(n);
625 VectorArray<T> col(n);
626 VectorArray<T> v(n);
627 VectorArray<T> w(n);
628
629 for (int i = 0 ; i < n; i++) {
630 cc[i] = blas_l2norm2<T, U>(n, &a[i * n], 1); // norm2 returns double value
631 permute[i] = i;
632 }
633 k = 0;
634 {
635 U tmp(0.0);
636 for (int i = 0; i < n; i++) {
637 if (cc[i] > tmp) {
638 tmp = cc[i];
639 k = i; // find the first entry that attains the maximum value
640 }
641 } // loop : i
642 }
643 n0 = 0;
644 for (int m = 0; m < n; m++) {
645 if (k > m) { // swap k-th and m-th columns of A[]
646 int kk = permute[m];
647 permute[m] = permute[k];
648 permute[k] = kk;
649 for (int i = 0; i < n; i++) {
650 col[i] = a[i + m * n];
651 }
652 for (int i = 0; i < n; i++) {
653 a[i + m * n] = a[i + k * n];
654 }
655 for (int i = 0; i < n; i++) {
656 a[i + k * n] = col[i];
657 }
658 U c = cc[m];
659 cc[m] = cc[k];
660 cc[k] = c;
661 } // if (k > m)
662 int nm = n - m;
663 T gamma;
664 HouseholderVector<T>(nm, &a[m + m * n], v.addrCoefs(), &gamma);
665
666 HouseholderReflection<T>(nm, &a[m + m * n], n,
667 v.addrCoefs(), w.addrCoefs(), gamma);
668 for (int i = (m + 1); i < n; i++) {
669 a[i + m * n] = Tzero; // = v[i] : to keep Householder matrix
670 }
671 for (int i = (m + 1); i < n; i++) {
672 cc[i] = blas_l2norm2<T, U>((n - m - 1), &a[m + 1 + i * n], 1);
673 }
674 U tt(0.0);
675 for (int i = (m + 1); i < n; i++) {
676 if (cc[i] > tt) {
677 tt = cc[i];
678 k = i; // find the first entry that attains the maximum value
679 }
680 } // loop : i
681 if (tt == Uzero) {
682 n0 = n - (m + 1);
683 break;
684 }
685 } // loop : m
686
687 return (n - n0);
688 }
689
690 template
691 int hqr_pivot<double, double>(const int n, double *a, int *permute);
692
693 template
694 int hqr_pivot<complex<double>, double>(const int n, complex<double> *a,
695 int *permute);
696
697 template
698 int hqr_pivot<quadruple, quadruple>(const int n, quadruple *a, int *permute);
699
700 template
701 int hqr_pivot<complex<quadruple>, quadruple>(const int n,
702 complex<quadruple> *a,
703 int *permute);
704 template
705 int hqr_pivot<float, float>(const int n, float *a, int *permute);
706
707 template
708 int hqr_pivot<complex<float>, float>(const int n, complex<float> *a,
709 int *permute);
710
711 //
712
713
714 template<typename T, typename U, typename W, typename Y>
715 bool ComputeDimKernel_(int *n0, bool *flag_unsym_permute,
716 const T *a_, const int n,
717 const bool sym_flag,
718 const int dim_augkern,
719 const U eps_machine, // for perturbation
720 const double eps_piv,
721 const bool verbose,
722 FILE *fp)
723 {
724 const W zero(0.0);
725 const Y Yzero(0.0);
726 const Y Yone(1.0);
727 const U Uzero(0.0);
728 Y Yeps_machine;
729 Yeps_machine = conv_prec<Y, U>(eps_machine);
730 // dimension of the image of the matrix a is at least one
731 int nn0, n1, n2;
732 int n_dim = n + 1;
733 int *permute = new int[n_dim];
734
735 ColumnMatrix<W> aq0(n_dim, n_dim);
736 ColumnMatrix<T> ad0(n, n);
737 ColumnMatrix<W> a1(n_dim, n_dim);
738 ColumnMatrix<W> aq_fact(n_dim, n_dim);
739 ColumnMatrix<T> ad_fact(n, n);
740 VectorArray<W> aa_diag(n_dim);
741 // VectorArray<Y> diag_scale(n_dim);
742 VectorArray<double> rr(n_dim - 1);
743
744 int *permute_d = new int[n_dim];
745 int *permute_q = new int[n_dim];
746
747 int *permute_right = new int[n_dim];
748 int *permute_left = new int[n_dim];
749 bool flag_tmp;
750 for (int i = 0; i < n; i++) {
751 for (int j = 0; j < n; j++) {
752 a1(i, j) = conv_prec<W, T>(a_[i + j * n]);
753 }
754 }
755 if (sym_flag) {
756 flag_tmp = false;
757 for (int i = 0; i < n; i++) {
758 permute_left[i] = permute_right[i] = i;
759 }
760 }
761 else {
762 double pivot = 1.0;
763 double fop;
764 double epspiv = todouble<U>(eps_machine);
765 ldu_full_permute<W, Y>(&nn0, 0, n, a1.addrCoefs(), n_dim, &pivot,
766 permute_right, permute_left,
767 epspiv, &fop);
768 flag_tmp = false;
769 for (int i = 0; i < n; i++) {
770 if (permute_left[i] != permute_right[i]) {
771 flag_tmp = true;
772 break;
773 }
774 }
775 }
776 diss_printf(verbose, fp, "%s %d : %s pivots\n",
777 __FILE__, __LINE__,
778 flag_tmp ? "full" : "symmetric ");
779 for (int i = 0; i < n; i++) {
780 diss_printf(verbose, fp, "%d : %d %d %s\n",
781 i, permute_left[i], permute_right[i],
782 tostring<W>(a1(i, i)).c_str());
783 // tostring<T>(tolower<W, T>(diag_scale[i])).c_str());
784 }
785 for (int j = 0; j < n; j++) {
786 for (int i = 0; i < n; i++) {
787 a1(i, j) = conv_prec<W, T>(a_[permute_left[i] + permute_right[j] * n]);
788 }
789 }
790 diss_printf(verbose, fp, "%s %d : permuted Schur complement %d\n",
791 __FILE__, __LINE__, n);
792 for (int i = 0; i < n; i++) {
793 diss_printf(verbose, fp, "%d ", i);
794 for (int j = 0; j < n; j++) {
795 diss_printf(verbose, fp, "%s ",
796 tostring<T>(conv_prec<T, W>(a1(i, j))).c_str());
797 }
798 diss_printf(verbose, fp, "\n");
799 }
800 for (int i = 0; i < n; i++) {
801 W tmp = zero;
802 for (int j = 0; j < n; j++) {
803 tmp += a1(i, j) + (random_bool() ? Yeps_machine : Yzero);
804 }
805 a1(i, n) = tmp;
806 a1(n, n) += tmp + (random_bool() ? Yeps_machine : Yzero);
807 }
808 for (int j = 0; j < n; j++) {
809 W tmp = zero;
810 for (int i = 0; i < n; i++) {
811 tmp += a1(i, j) + (random_bool() ? Yeps_machine : Yzero);
812 }
813 a1(n, j) = tmp;
814 }
815 // column and row of inflated matrix are scaled
816 Y diag_scalen = sqrt(Yone / blas_abs<W, Y>(a1(n, n)));
817 for (int i = 0; i < n; i++) {
818 a1(i, n) *= diag_scalen;
819 a1(n, i) *= diag_scalen;
820 }
821 a1(n, n) *= (diag_scalen * diag_scalen);
822
823 diss_printf(verbose, fp, "%s %d : the original Schur complement %d\n",
824 __FILE__, __LINE__, n);
825 for (int i = 0; i < n; i++) {
826 diss_printf(verbose, fp, "%d ", i);
827 for (int j = 0; j < n; j++) {
828 diss_printf(verbose, fp, "%s ",
829 tostring<T>(conv_prec<T, W>(a_[i + j * n])).c_str());
830 }
831 diss_printf(verbose, fp, "\n");
832 }
833
834 diss_printf(verbose, fp, "%s %d : the scaled last Schur complement %d\n",
835 __FILE__, __LINE__, n_dim);
836 for (int i = 0; i < n_dim; i++) {
837 diss_printf(verbose, fp, "%d ", i);
838 for (int j = 0; j < n_dim; j++) {
839 diss_printf(verbose, fp, "%s ",
840 tostring<T>(conv_prec<T, W>(a1(i,j))).c_str());
841 }
842 diss_printf(verbose, fp, "\n");
843 }
844 aq0.copy(a1);
845 aq_fact.copy(a1);
846 n1 = hqr_pivot<W, Y>(n_dim, aq0.addrCoefs(), permute);
847 diss_printf(verbose, fp,
848 "%s %d dimension of the image deteced by d_hqr_pivot() is %d\n",
849 __FILE__, __LINE__, n1);
850 diss_printf(verbose, fp, "%s %d QR\n", __FILE__, __LINE__);
851 for (int i = 0; i < n_dim; i++) {
852 diss_printf(verbose, fp, "%d : %d ", i, permute[i]);
853 for (int j = 0; j < n_dim; j++) {
854 diss_printf(verbose, fp, "%s ",
855 tostring<T>(conv_prec<T, W>(aq0(i, j))).c_str());
856 }
857 diss_printf(verbose, fp, "\n");
858 }
859 for (int i = 0; i < n1; i++) {
860 aa_diag[i] = aq0(i, i);
861 }
862
863 list<int> pos_gap;
864 vector<int> kernel_dim;
865 pos_gap.push_back(dim_augkern);
866
867 for (int i = 0; i < (n1 - 1); i++) {
868 rr[i] = todouble<Y>(blas_abs<W, Y>(aa_diag[i + 1] / aa_diag[i]));
869 }
870 // find largest gap inside of invertible part
871 double aug_diff = 1.0;
872 for (int i = 0; i < (dim_augkern - 1); i++) {
873 if (aug_diff > rr[i]) {
874 aug_diff = rr[i];
875 }
876 }
877
878 diss_printf(verbose, fp, "%s %d : aug_diff = %s esp = %.12e\n",
879 __FILE__, __LINE__,
880 tostring<double>(aug_diff).c_str(), eps_piv);
881 for (int i = (dim_augkern - 1); i < (n1 - 1); i++) {
882 if (rr[i] < (aug_diff * eps_piv)) {
883 diss_printf(verbose, fp, "rr[%d] : %s\n",
884 i, tostring<double>(rr[i]).c_str());
885 pos_gap.push_back(i + 1);
886 }
887 }
888 const bool flag_perturb =
889 ((rr[dim_augkern - 1] < aug_diff)
890 && (blas_abs<W, Y>(aa_diag[n1 - 1]) > Yeps_machine * Y(eps_piv)));
891
892 const U eps_perturb = flag_perturb ? eps_machine : Uzero;
893 diss_printf(verbose, fp, "%s %d : rr[%d] = %s => perturb = %s %s\n",
894 __FILE__, __LINE__,
895 (dim_augkern - 1),
896 tostring<double>(rr[dim_augkern - 1]).c_str(),
897 tostring<U>(eps_perturb).c_str(),
898 tostring<Y>(blas_abs<W, Y>(aa_diag[n1 - 1])).c_str()
899 );
900
901 int n_dim1;
902 if (flag_perturb) { // condition number of the invertible part is moderate
903 n2 = n1; // and the diagonal entry becomes etreamly small
904 // n1 may be less than n_dim when a diagnal of QR == 0
905 for (int i = 0; i < (n1 - 1); i++) {
906 if (rr[i] < (todouble<U>(eps_machine) / sqrt(eps_piv))) {
907 n2 = i + 1;
908 break;
909 }
910 }
911 n_dim1 = n2 > dim_augkern ? n2 : n_dim;
912 pos_gap.push_back(n2 - 1); // matrix being inflated
913 }
914 else {
915 n_dim1 = n_dim;
916 pos_gap.push_back(n); // matrix being inflated : n = n_dim - 1
917 }
918 rr.free();
919 pos_gap.sort();
920 pos_gap.unique();
921
922 for (list<int>::const_iterator it = pos_gap.begin(); it != pos_gap.end();
923 ++it) {
924 kernel_dim.push_back(n_dim1 - (*it));
925 }
926 diss_printf(verbose, fp, "%s %d : kernel_dim = %d : ",
927 __FILE__, __LINE__, (int)kernel_dim.size());
928 for (vector<int>::const_iterator it = kernel_dim.begin();
929 it != kernel_dim.end();
930 ++it) {
931 diss_printf(verbose, fp, "%d ", *it);
932 }
933 diss_printf(verbose, fp, "\n");
934
935 int flag;
936 flag = VerifyDimKernel<T, U, W, Y>(&nn0, permute_q,
937 n_dim1, aq_fact.addrCoefs(), kernel_dim,
938 sym_flag, dim_augkern, eps_perturb,
939 verbose, fp);
940 if (flag == false) {
941 nn0 = 1; // iflated matrix is generated as singular
942 }
943 // nn0 += (n_dim - n2) - 1;
944 // nn0--; // detection of kernel is done for dim_augkern > 0 and at least
945 // if (nn0 > 0) {
946 {
947 const double eps_machine_double = todouble<U>(eps_machine);
948 U *errors_d = new U[nn0 + 1];
949 list<int> nnn;
950 if (nn0 > 2) {
951 nnn.push_back(nn0 - 2);
952 }
953 nnn.push_back(nn0 - 1); //
954 nnn.push_back(nn0);
955
956 for (int j = 0; j < n; j++) {
957 for (int i = 0; i < n; i++) {
958 ad_fact(i, j) = a_[i + j * n];
959 }
960 }
961 {
962 double pivot_ref = 0.0;
963 for (int i = 0; i < n ; i++) {
964 double tmp = blas_abs<T, double>(a_[i + i * n]);
965 pivot_ref = pivot_ref > tmp ? pivot_ref : tmp;
966 }
967 int nnn0;
968 double fop;
969 if (sym_flag) {
970 full_ldlt_permute<T, U>(&nnn0, 0, n, ad_fact.addrCoefs(), n,
971 &pivot_ref, permute_d, eps_machine_double,
972 &fop);
973 }
974 else {
975 full_ldu_permute<T, U>(&nnn0, 0, n, ad_fact.addrCoefs(), n,
976 &pivot_ref, permute_d, eps_machine_double,
977 &fop);
978 }
979 }
980 for (int j = 0; j < n; j++) {
981 for (int i = 0; i < n; i++) {
982 ad0(i, j) = a_[permute_d[i] + permute_d[j] * n];
983 }
984 }
985 diss_printf(verbose, fp, "%s %d : verify errors : size = %d : ",
986 __FILE__, __LINE__, nnn.size());
987 for (list<int>::const_iterator it = nnn.begin(); it != nnn.end();
988 ++it) {
989 diss_printf(verbose, fp, "%d ", (*it));
990 }
991 diss_printf(verbose, fp, "\n");
992 for (list<int>::const_iterator it = nnn.begin(); it != nnn.end();
993 ++it) {
994 const int nn = (*it);
995 if (nn > 0) {
996 verify_kernels<T, U>(nn, n, ad0.addrCoefs(), ad_fact.addrCoefs(),
997 n,
998 eps_machine_double, errors_d,
999 verbose, fp);
1000 diss_printf(verbose, fp, "errors of %d kernels\n", nn);
1001 for (int i = 0; i < nn; i++) {
1002 diss_printf(verbose, fp,
1003 "%d : %s\n", i, tostring<U>(errors_d[i]).c_str());
1004 }
1005 }
1006 }
1007 if (flag_tmp) {
1008 for (int j = 0; j < n; j++) {
1009 for (int i = 0; i < n; i++) {
1010 ad_fact(i, j) = a_[permute_left[i] + permute_right[j] * n];
1011 }
1012 }
1013 {
1014 double pivot_ref = 0.0;
1015 for (int i = 0; i < n ; i++) {
1016 double tmp = blas_abs<T, double>(a_[i + i * n]);
1017 pivot_ref = pivot_ref > tmp ? pivot_ref : tmp;
1018 }
1019 int nnn0;
1020 double fop;
1021 if (sym_flag) {
1022 full_ldlt_permute<T, U>(&nnn0, 0, n, ad_fact.addrCoefs(), n,
1023 &pivot_ref, permute_d, eps_machine_double,
1024 &fop);
1025 }
1026 else {
1027 full_ldu_permute<T, U>(&nnn0, 0, n, ad_fact.addrCoefs(), n,
1028 &pivot_ref, permute_d, eps_machine_double,
1029 &fop);
1030 }
1031 }
1032 for (int j = 0; j < n; j++) {
1033 for (int i = 0; i < n; i++) {
1034 ad0(i, j) = a_[permute_d[permute_left[i]] + permute_d[permute_right[j]] * n];
1035 }
1036 }
1037 diss_printf(verbose, fp, "%s %d : verify errors : size = %d : ",
1038 __FILE__, __LINE__, nnn.size());
1039 for (list<int>::const_iterator it = nnn.begin(); it != nnn.end();
1040 ++it) {
1041 diss_printf(verbose, fp, "%d ", (*it));
1042 }
1043 diss_printf(verbose, fp, "\n");
1044 for (list<int>::const_iterator it = nnn.begin(); it != nnn.end();
1045 ++it) {
1046 const int nn = (*it);
1047 if (nn > 0) {
1048 verify_kernels<T, U>(nn, n, ad0.addrCoefs(), ad_fact.addrCoefs(), n,
1049 eps_machine_double, errors_d,
1050 verbose, fp);
1051 diss_printf(verbose, fp, "errors of %d kernels\n", nn);
1052 for (int i = 0; i < nn; i++) {
1053 diss_printf(verbose, fp,
1054 "%d : %s\n", i, tostring<U>(errors_d[i]).c_str());
1055 }
1056 }
1057 }
1058 } // if (flag_tmp)
1059 // nnn.clear();
1060 Y *errors_q = new Y[nn0 + 1];
1061
1062 for (int j = 0; j < n_dim; j++) {
1063 for (int i = 0; i < n_dim; i++) {
1064 aq0(i, j) = a1(permute_q[i], permute_q[j]);
1065 }
1066 }
1067
1068 for (list<int>::const_iterator it = nnn.begin(); it != nnn.end();
1069 ++it) {
1070 const int nn = (*it) + 1;
1071 verify_kernels<W, Y>(nn, n_dim,
1072 aq0.addrCoefs(), aq_fact.addrCoefs(), n_dim,
1073 eps_machine_double, errors_q,
1074 verbose, fp);
1075 diss_printf(verbose, fp, "errors of %d kernels\n", nn);
1076 for (int i = 0; i < nn; i++) {
1077 diss_printf(verbose, fp,
1078 "%d : %s\n", i,
1079 tostring<Y>(errors_q[i]).c_str());
1080 }
1081 }
1082
1083
1084 for (int j = 0; j < n; j++) {
1085 for (int i = 0; i < n; i++) {
1086 aq_fact(i, j) = conv_prec<W, T>(a_[i + j * n]);
1087 }
1088 }
1089 {
1090 double pivot_ref = 0.0;
1091 for (int i = 0; i < n ; i++) {
1092 double tmp = blas_abs<T, double>(a_[i + i * n]);
1093 pivot_ref = pivot_ref > tmp ? pivot_ref : tmp;
1094 }
1095 int nnn0;
1096 double fop;
1097 if (sym_flag) {
1098 full_ldlt_permute<W, Y>(&nnn0, 0, n, aq_fact.addrCoefs(), n_dim,
1099 &pivot_ref, permute_q, eps_machine_double,
1100 &fop);
1101 }
1102 else {
1103 full_ldu_permute<W, Y>(&nnn0, 0, n, aq_fact.addrCoefs(), n_dim,
1104 &pivot_ref, permute_q, eps_machine_double,
1105 &fop);
1106 }
1107 }
1108 for (int j = 0; j < n; j++) {
1109 for (int i = 0; i < n; i++) {
1110 aq0(i, j) = conv_prec<W, T>(a_[permute_q[i] + permute_q[j] * n]);
1111 }
1112 }
1113 diss_printf(verbose, fp, "%s %d : verify errors : size = %d : ",
1114 __FILE__, __LINE__, nnn.size());
1115 for (list<int>::const_iterator it = nnn.begin(); it != nnn.end();
1116 ++it) {
1117 diss_printf(verbose, fp, "%d ", (*it));
1118 }
1119 diss_printf(verbose, fp, "\n");
1120 for (list<int>::const_iterator it = nnn.begin(); it != nnn.end();
1121 ++it) {
1122 const int nn = (*it);
1123 if (nn > 0) {
1124 verify_kernels<W, Y>(nn, n,
1125 aq0.addrCoefs(), aq_fact.addrCoefs(), n_dim,
1126 eps_machine_double, errors_q,
1127 verbose, fp);
1128 diss_printf(verbose, fp, "errors of %d kernels\n", nn);
1129 for (int i = 0; i < nn; i++) {
1130 diss_printf(verbose, fp,
1131 "%d : %s\n", i, tostring<Y>(errors_q[i]).c_str());
1132 }
1133 }
1134 }
1135
1136 nnn.clear();
1137 delete [] errors_q;
1138 delete [] errors_d;
1139 } // if (nn0 > 0)
1140 delete [] permute;
1141 delete [] permute_d;
1142 delete [] permute_q;
1143 delete [] permute_left;
1144 delete [] permute_right;
1145 *n0 = nn0 + (n_dim - n_dim1) - 1;
1146 diss_printf(verbose, fp,
1147 "%s %d : dimension of the kernel is %d\n",
1148 __FILE__, __LINE__, *n0);
1149
1150
1151
1152 *flag_unsym_permute = flag_tmp;
1153
1154 return flag;
1155 }
1156
1157 template
1158 bool ComputeDimKernel_<double, double,
1159 quadruple, quadruple>(int *n0, bool *flag_unsym_permute,
1160 const double *a_,
1161 const int n,
1162 const bool sym_flag,
1163 const int dim_augkern,
1164 const double eps_machine,
1165 const double eps_piv,
1166 const bool verbose,
1167 FILE *fp);
1168
1169 template
1170 bool ComputeDimKernel_<complex<double>,
1171 double,
1172 complex<quadruple>,
1173 quadruple>(int *n0, bool *flag_unsym_permute,
1174 const complex<double> *a_,
1175 const int n,
1176 const bool sym_flag,
1177 const int dim_augkern,
1178 const double eps_machine,
1179 const double eps_piv,
1180 const bool verbose,
1181 FILE *fp);
1182
1183 template
1184 bool ComputeDimKernel_<quadruple,
1185 quadruple,
1186 octruple,
1187 octruple>(int *n0, bool *flag_unsym_permute,
1188 const quadruple *a_,
1189 const int n,
1190 const bool sym_flag,
1191 const int dim_augkern,
1192 const quadruple eps_machine,
1193 const double eps_piv,
1194 const bool verbose,
1195 FILE *fp);
1196
1197 template
1198 bool ComputeDimKernel_<complex<quadruple>,
1199 quadruple,
1200 complex<octruple>,
1201 octruple>(int *n0, bool *flag_unsym_permute,
1202 const complex<quadruple> *a_,
1203 const int n,
1204 const bool sym_flag,
1205 const int dim_augkern,
1206 const quadruple eps_machine,
1207 const double eps_piv,
1208 const bool verbose,
1209 FILE *fp);
1210
1211
1212 template<typename T, typename U>
1213 bool ComputeDimKernel(int *n0, bool *flag_unsym_permute,
1214 const T *a_, const int n,
1215 const bool sym_flag,
1216 const int dim_augkern,
1217 const U eps_machine, // for perturbation
1218 const double eps_piv,
1219 const bool verbose,
1220 FILE *fp)
1221 {
1222 fprintf(stderr, "%s %d : specialized template not implemented\n",
1223 __FILE__, __LINE__);
1224 }
1225
1226 template<>
1227 bool ComputeDimKernel<double, double>(int *n0, bool *flag_unsym_permute,
1228 const double *a_,
1229 const int n,
1230 const bool sym_flag,
1231 const int dim_augkern,
1232 const double eps_machine,
1233 const double eps_piv,
1234 const bool verbose,
1235 FILE *fp)
1236 {
1237 return ComputeDimKernel_<double,
1238 double,
1239 quadruple,
1240 quadruple>(n0, flag_unsym_permute, a_, n,
1241 sym_flag, dim_augkern,
1242 eps_machine, eps_piv,
1243 verbose, fp);
1244 }
1245
1246 template<>
1247 bool ComputeDimKernel<complex<double>,
1248 double>(int *n0, bool *flag_unsym_permute,
1249 const complex<double> *a_,
1250 const int n,
1251 const bool sym_flag,
1252 const int dim_augkern,
1253 const double eps_machine,
1254 const double eps_piv,
1255 const bool verbose,
1256 FILE *fp)
1257 {
1258 return ComputeDimKernel_<complex<double>,
1259 double,
1260 complex<quadruple>,
1261 quadruple>(n0, flag_unsym_permute, a_, n,
1262 sym_flag, dim_augkern,
1263 eps_machine, eps_piv,
1264 verbose, fp);
1265
1266 }
1267
1268 template<>
1269 bool ComputeDimKernel<quadruple,
1270 quadruple>(int *n0, bool *flag_unsym_permute,
1271 const quadruple *a_,
1272 const int n,
1273 const bool sym_flag,
1274 const int dim_augkern,
1275 const quadruple eps_machine,
1276 const double eps_piv,
1277 const bool verbose,
1278 FILE *fp)
1279 {
1280 return ComputeDimKernel_<quadruple,
1281 quadruple,
1282 octruple,
1283 octruple>(n0, flag_unsym_permute, a_, n,
1284 sym_flag, dim_augkern,
1285 eps_machine, eps_piv,
1286 verbose, fp);
1287 }
1288
1289 template<>
1290 bool ComputeDimKernel<complex<quadruple>,
1291 quadruple>(int *n0, bool *flag_unsym_permute,
1292 const complex<quadruple> *a_,
1293 const int n,
1294 const bool sym_flag,
1295 const int dim_augkern,
1296 const quadruple eps_machine,
1297 const double eps_piv,
1298 const bool verbose,
1299 FILE *fp)
1300 {
1301 return ComputeDimKernel_<complex<quadruple>,
1302 quadruple,
1303 complex<octruple>,
1304 octruple>(n0, flag_unsym_permute, a_, n,
1305 sym_flag, dim_augkern,
1306 eps_machine, eps_piv,
1307 verbose, fp);
1308 }
1309
1310 template<>
1311 bool ComputeDimKernel<float, float>(int *n0, bool *flag_unsym_permute,
1312 const float *a_,
1313 const int n,
1314 const bool sym_flag,
1315 const int dim_augkern,
1316 const float eps_machine,
1317 const double eps_piv,
1318 const bool verbose,
1319 FILE *fp)
1320 {
1321 return ComputeDimKernel_<float,
1322 float,
1323 double,
1324 double>(n0, flag_unsym_permute, a_, n,
1325 sym_flag, dim_augkern,
1326 eps_machine, eps_piv,
1327 verbose, fp);
1328 }
1329
1330 template<>
1331 bool ComputeDimKernel<complex<float>,
1332 float>(int *n0, bool *flag_unsym_permute,
1333 const complex<float> *a_,
1334 const int n,
1335 const bool sym_flag,
1336 const int dim_augkern,
1337 const float eps_machine,
1338 const double eps_piv,
1339 const bool verbose,
1340 FILE *fp)
1341 {
1342 return ComputeDimKernel_<complex<float>,
1343 float,
1344 complex<double>,
1345 double>(n0, flag_unsym_permute, a_, n,
1346 sym_flag, dim_augkern,
1347 eps_machine, eps_piv,
1348 verbose, fp);
1349
1350 }
1351
1352
1353 //
1354
1355 template<typename T, typename U, typename W, typename Y>
1356 bool VerifyDimKernel(int *nn0_,
1357 int *permute_q,
1358 int n_dim, W* a_fact,
1359 vector<int> &kernel_dim,
1360 const bool sym_flag,
1361 const int dim_augkern,
1362 const U eps_machine,
1363 const bool verbose,
1364 FILE *fp)
1365 {
1366 U Uzero(0.0);
1367 U Uone(1.0);
1368 int nn, nn0;
1369 int k;
1370 double pivot_ref, pivot_ref_q;
1371 // int *permute_q = new int[n_dim];
1372 ColumnMatrix<W> a2(n_dim, n_dim);
1373 U *errors = new U[6];
1374
1375 blas_copy<W>((n_dim * n_dim), a_fact, 1, a2.addrCoefs(), 1);
1376 // for (int i = 0; i < (n_dim * n_dim); i++) {
1377 // a2[i] = a_fact[i];
1378 // }
1379 pivot_ref = 0.0;
1380 k = 0;
1381 for (int i = 0; i < n_dim; i++) {
1382 double dtmp = blas_abs<W, double>(a_fact[k]); // accuracy? : 14 Jul.2015 Atsushi
1383 k += (n_dim + 1);
1384 pivot_ref = (pivot_ref < dtmp ? dtmp : pivot_ref);
1385 }
1386 pivot_ref_q = pivot_ref;
1387 diss_printf(verbose, fp,
1388 "pivot_ref_q = %.12e\n", pivot_ref_q);
1389 const int nn1 = 1; // matrix has at least one dimensional kernel
1390 // qfull_sym_gauss_part is only used to get permute_q[]
1391
1392 if (sym_flag) {
1393 double fop;
1394 const double eps0 = todouble<U>(eps_machine);
1395 full_ldlt_permute<W, Y>(&nn, nn1, n_dim, a_fact, n_dim, &pivot_ref_q,
1396 permute_q, eps0, &fop);
1397 }
1398 else {
1399 double fop;
1400 const double eps0 = todouble<U>(eps_machine);
1401 full_ldu_permute<W, Y>(&nn, nn1, n_dim, a_fact, n_dim, &pivot_ref_q,
1402 permute_q, eps0, &fop);
1403 }
1404 // question: eps_machine is ok? : 06 Jan.2013
1405 // => jump between diagonal is within double precision : 27 Jan.2013
1406 diss_printf(verbose, fp,
1407 "%s %d : permutation : ", __FILE__, __LINE__);
1408 for (int i = 0; i < n_dim; i++) {
1409 diss_printf(verbose, fp, "%d ", permute_q[i]);
1410 }
1411 diss_printf(verbose, fp, "\n");
1412 vector<int> dims(n_dim);
1413 for (int i = 0; i < n_dim; i++) {
1414 dims[i] = i + 1;
1415 }
1416 vector<U> errors_image(dims.size());
1417 U error_max, error_min, Ueps;
1418 error_min = Uone / eps_machine;
1419 error_max = Uzero;
1420 Ueps = machine_epsilon<U, U>();
1421 for (int i = 0; i < dims.size(); i++) {
1422 errors_image[i] = check_matrixerr<T, U, W, Y>(n_dim, n_dim,
1423 a2.addrCoefs(), dim_augkern,
1424 dims[i],
1425 permute_q,
1426 eps_machine,
1427 sym_flag);
1428 }
1429 for (int i = 0; i < dims.size(); i++) {
1430 diss_printf(verbose, fp,
1431 "%d : %s\n", dims[i], tostring<U>(errors_image[i]).c_str());
1432 }
1433
1434 U err_image = errors_image[0];
1435 for (int i = 1; i < dims.size(); i++) {
1436 if (dims[i] > dim_augkern) {
1437 break;
1438 }
1439 err_image = err_image < errors_image[i] ? errors_image[i] : err_image;
1440 }
1441 int count_err_image_updated = 0;
1442 int dim_image = dim_augkern;
1443 diss_printf(verbose, fp,
1444 "err_image = %s ", tostring<U>(err_image).c_str());
1445 U eps_param0 = sqrt<U>(err_image * errors_image.back());
1446 bool flag = false;
1447 bool flag0 = false;
1448 diss_printf(verbose, fp,
1449 "eps_param0 = %s\n", tostring<U>(eps_param0).c_str());
1450 for (vector<int>::const_iterator it = kernel_dim.begin();
1451 it != kernel_dim.end(); ++it) {
1452 nn0 = *it;
1453
1454 flag0 = check_kern<T, U, W, Y>(nn0, n_dim, n_dim, a2.addrCoefs(),
1455 permute_q,
1456 dim_augkern, eps_machine,
1457 eps_param0, sym_flag, errors,
1458 verbose, fp);
1459 diss_printf(verbose, fp, "%d : %s / %s / %s\n",
1460 nn0,
1461 tostring<U>(errors[0]).c_str(), tostring<U>(errors[1]).c_str(),
1462 tostring<U>(errors[2]).c_str());
1463 // if (nn0 > 1) {
1464 if (!flag0 && (nn0 > 1)) {
1465 diss_printf(verbose, fp,
1466 "first trial by error from image %d %s -> %s fails\n",
1467 n_dim, tostring<U>(errors_image.back()).c_str(),
1468 tostring<U>(eps_param0).c_str());
1469 flag0 = check_kern<T, U, W, Y>((nn0 - 1), n_dim, n_dim, a2.addrCoefs(),
1470 permute_q,
1471 dim_augkern, eps_machine,
1472 eps_param0, sym_flag,
1473 &errors[3], verbose, fp);
1474 diss_printf(verbose, fp, "%d : %s / %s / %s\n",
1475 (nn0 - 1), tostring<U>(errors[3]).c_str(),
1476 tostring<U>(errors[4]).c_str(),
1477 tostring<U>(errors[5]).c_str());
1478 diss_printf(verbose, fp, "diff = %s\n",
1479 tostring<U>(errors[0] - errors[4]).c_str());
1480 // criteria of equality
1481 U xtmp = ((fabs(errors[0]) > fabs(errors[4])) ?
1482 fabs(errors[0]) : fabs(errors[4]));
1483 xtmp = sqrt<U>(xtmp * eps_machine);
1484 U eps_param1 = (errors[3] + errors[4]) / U(2);
1485 eps_param1 = sqrt<U>(eps_param1 * err_image);
1486 eps_param0 = sqrt<U>(err_image * errors_image.back());
1487 diss_printf(verbose, fp, "%s + %s = %s / %s\n",
1488 tostring<U>(errors[3]).c_str(),
1489 tostring<U>(errors[4]).c_str(),
1490 tostring<U>(eps_param1).c_str(),
1491 tostring<U>(eps_param0).c_str());
1492 if (errors[3] < eps_param0) {
1493 diss_printf(verbose, fp, "not satisfies the condition %s < %s\n",
1494 tostring<U>(eps_param0).c_str(),
1495 tostring<U>(errors[3]).c_str());
1496 int itmp = n_dim - nn0;
1497 U err_image_tmp;
1498
1499 err_image_tmp = check_matrixerr<T, U, W, Y>(n_dim, n_dim,
1500 a2.addrCoefs(),
1501 dim_augkern,
1502 itmp,
1503 permute_q,
1504 eps_machine,
1505 sym_flag);
1506 diss_printf(verbose, fp,
1507 "part of %d (%d - %d) is regular, err_image=%s/%s\n",
1508 itmp, n_dim, nn0,
1509 tostring<U>(err_image_tmp).c_str(),
1510 tostring<U>(err_image).c_str());
1511 if (err_image < err_image_tmp) {
1512 dim_image = itmp;
1513 count_err_image_updated++;
1514 err_image = err_image_tmp;
1515 }
1516 continue;
1517 }
1518 if ((errors[0] > eps_param1) && (errors[1] < eps_param1)) {
1519 if ((fabs(errors[0] - errors[4]) < xtmp)) {
1520 diss_printf(verbose, fp, "found with %d dim. %d updated\n",
1521 dim_image, count_err_image_updated);
1522 }
1523 else{
1524 diss_printf(verbose, fp,
1525 "found with %d dim. %d updated, needs be refactorized\n",
1526 dim_image, count_err_image_updated);
1527 }
1528 flag = true;
1529 break;
1530 }
1531 } // if (nn0 > 0)
1532 else {
1533 if (flag0) {
1534 diss_printf(verbose, fp, "found\n");
1535 flag = true;
1536 break;
1537 }
1538 }
1539 } // loop : it
1540 if (!flag) {
1541 diss_printf(verbose, fp, "kernel detection routine does not work : ");
1542 if (kernel_dim.size() == 1) {
1543 diss_printf(verbose, fp, "detection by Householder = %d\n", nn0);
1544 nn0 = 0;
1545 // n0 = kernel_dim.front();
1546 }
1547 else {
1548 diss_printf(verbose, fp, "unclear : ");
1549 nn0 = kernel_dim.front();
1550 for (vector<int>::const_iterator it = kernel_dim.begin();
1551 it != kernel_dim.end(); it++) {
1552 diss_printf(verbose, fp, "%d ", (*it));
1553 if (((*it) + dim_augkern) != n_dim) {
1554 nn0 = (*it);
1555 diss_printf(verbose, fp, " / ");
1556 }
1557 else {
1558 diss_printf(verbose, fp, "+ %d = %d /", dim_augkern, n_dim);
1559 }
1560 }
1561 diss_printf(verbose, fp, "\n");
1562 diss_printf(verbose, fp, "detection by Householder = %d\n", nn0);
1563 }
1564 }
1565 else {
1566 if ((kernel_dim.size() == 1) && (kernel_dim.front() != nn0)) {
1567 if (nn0 != 1) {
1568 diss_printf(verbose, fp, "strange_matrix\n");
1569 nn0 = 0;
1570 flag = false;
1571 }
1572 }
1573 }
1574 // delete [] a2;
1575 delete [] errors;
1576 // delete [] permute_q;
1577 *nn0_ = nn0;
1578 return flag;
1579 }
1580
1581 template
1582 bool VerifyDimKernel<double, double,
1583 quadruple, quadruple>(int *nn0_,
1584 int *permute_q,
1585 int n_dim,
1586 quadruple* a_fact,
1587 vector<int>& kernel_dim,
1588 const bool sym_flag,
1589 const int dim_augkern,
1590 const double eps_machine,
1591 const bool verbose,
1592 FILE *fp);
1593 template
1594 bool VerifyDimKernel<complex<double>, double,
1595 complex<quadruple>, quadruple>(int *nn0_,
1596 int *permute_q,
1597 int n_dim,
1598 complex<quadruple>* a_fact,
1599 vector<int>& kernel_dim,
1600 const bool sym_flag,
1601 const int dim_augkern,
1602 const double eps_machine,
1603 const bool verbose,
1604 FILE *fp);
1605 #ifndef NO_OCTRUPLE
1606 template
1607 bool VerifyDimKernel<quadruple, quadruple,
1608 octruple, octruple>(int *nn0_,
1609 int *permute_q,
1610 int n_dim,
1611 octruple* a_fact,
1612 vector<int>& kernel_dim,
1613 const bool sym_flag,
1614 const int dim_augkern,
1615 const quadruple eps_machine,
1616 const bool verbose,
1617 FILE *fp);
1618 template
1619 bool VerifyDimKernel<complex<quadruple>, quadruple,
1620 complex<octruple>, octruple>(int *nn0_,
1621 int *permute_q,
1622 int n_dim,
1623 complex<octruple>* a_fact,
1624 vector<int>& kernel_dim,
1625 const bool sym_flag,
1626 const int dim_augkern,
1627 const quadruple eps_machine,
1628 const bool verbose,
1629 FILE *fp);
1630
1631 #endif
1632