/*! \file C_KernDetect.cpp
\brief Kernel detection algorithm : symm <= DOI: 10.1002/nme.4729 / unsymm
\author Atsushi. Suzuki, Laboratoire Jacques-Louis Lions
\date Jun. 20th 2014
\date Jul. 12th 2015
\date Nov. 30th 2016
*/
// This file is part of Dissection
//
// Dissection 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 3 of the License, or
// (at your option) any later version.
//
// Linking Dissection statically or dynamically with other modules is making
// a combined work based on Disssection. Thus, the terms and conditions of
// the GNU General Public License cover the whole combination.
//
// As a special exception, the copyright holders of Dissection give you
// permission to combine Dissection program with free software programs or
// libraries that are released under the GNU LGPL and with independent modules
// that communicate with Dissection solely through the Dissection-fortran
// interface. You may copy and distribute such a system following the terms of
// the GNU GPL for Dissection and the licenses of the other code concerned,
// provided that you include the source code of that other code when and as
// the GNU GPL requires distribution of source code and provided that you do
// not modify the Dissection-fortran interface.
//
// Note that people who make modified versions of Dissection are not obligated
// to grant this special exception for their modified versions; it is their
// choice whether to do so. The GNU General Public License gives permission to
// release a modified version without this exception; this exception also makes
// it possible to release a modified version which carries forward this
// exception. If you modify the Dissection-fortran interface, this exception
// does not apply to your modified version of Dissection, and you must remove
// this exception when you distribute your modified version.
//
// This exception is an additional permission under section 7 of the GNU
// General Public License, version 3 ("GPLv3")
//
// Dissection 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 Dissection. If not, see .
//
#include "Compiler/OptionLibrary.hpp"
#include "Driver/C_KernDetect.hpp"
#include "Algebra/ColumnMatrix.hpp"
#include "Algebra/VectorArray.hpp"
#include "Compiler/DissectionIO.hpp"
// T may be std::complex of U and W is in higher precision than T
template
bool check_kern(const int n0, const int lda, const int n, W *a_ini,
int *permute,
const int dim_augkern, const U &eps,
const U &eps_param, const bool flag_sym, U *errors,
const bool verbose, FILE *fp)
{
bool flag;
// W *a_q, *a_fq, *proj, *nsp, *nsp2;
// W *v, *alpha;
const W zero(0.0);
const W one(1.0);
const W none(-1.0);
const U Uzero(0.0);
ColumnMatrix a_q(n, n);
ColumnMatrix a_fq(n, n);
ColumnMatrix proj(n, n);
ColumnMatrix nsp(n, n);
ColumnMatrix nsp2(n,n);
VectorArray v(n);
VectorArray alpha(n);
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
const int ij = permute[i] + permute[j] * lda;
a_fq(i, j) = a_ini[ij];
}
}
// duplicate of a_fq
a_q.copy(a_fq);
if (flag_sym) {
full_ldlt(n, a_fq.addrCoefs(), n);
}
else {
full_ldu(n, a_fq.addrCoefs(), n);
}
int n1 = n - n0;
for (int j = 0; j < n0; j++) {
for (int i = 0; i < n1; i++) {
nsp(i, j) = a_q(i, (j + n1)); // nsp[i + j * n] = a_q[i + (j + n1) * n];
}
for (int i = n1; i < n; i++) {
nsp(i, j) = zero; // nsp[i + j * n] = zero;
}
nsp((n1 + j), j) = none;
}
full_fwbw_perturb_multi(n1, n0, a_q.addrCoefs(), n,
a_fq.addrCoefs(), nsp.addrCoefs(), dim_augkern,
eps,
flag_sym);
// compute projection matrix
for (int i = 0; i < n0; i++) {
for (int j = 0; j <= i; j++) {
proj(i, j) = blas_dot(n,
nsp.addrCoefs() + (i * n), 1,
nsp.addrCoefs() + (j * n), 1); // lower
proj(j, i) = blas_conj(proj(i, j)); // upper
}
}
// Hermite symmteric with complex inner product
full_ldlh(n0, proj.addrCoefs(), n);
for (int m = (n0 - 1); m <= (n0 + 1); m++) {
int k = n - m;
U res_err = U(0.0);
for (int j = 0; j < n; j++) {
for (int i = 0; i < k; i++) {
nsp2(i, j) = a_q(i, j); // nsp2[i + j * n] = a_q[i + j * n];
}
}
full_fwbw_perturb_multi(k, n, a_q.addrCoefs(), n,
a_fq.addrCoefs(), nsp2.addrCoefs(),
dim_augkern,
eps,
flag_sym);
for (int j = 0; j < n; j++) {
for (int i = k; i < n; i++) {
nsp2(i, j) = zero; // nsp2[i + j * n] = zero;
}
nsp2(j, j) -= one; // nsp2[j + j * n] -= one;
}
for (int j = 0; j < k; j++) {
for (int i = 0; i < n; i++) {
v[i] = nsp2(i, j); // v[i] = nsp2[i + j * n];
}
U res = conv_prec(blas_l2norm(n, v.addrCoefs(), 1));
res_err = res_err > res ? res_err : res;
}
for (int j = k; j < n; j++) {
for (int i = 0; i < n; i++) {
v[i] = nsp2(i, j); // v[i] = nsp2[i + j * n];
}
// alpha = 1; beta = 0;
blas_gemv(CblasTrans, n, n0, one,
nsp.addrCoefs(), n, v.addrCoefs(), 1,
zero, alpha.addrCoefs(), 1);
full_fwbw_part(n0, proj.addrCoefs(), n, alpha.addrCoefs());
// alpha = -1; beta = 1;
blas_gemv(CblasNoTrans, n, n0, none,
nsp.addrCoefs(), n, alpha.addrCoefs(), 1,
one, v.addrCoefs(), 1);
U res = conv_prec(blas_l2norm(n, v.addrCoefs(), 1));
res_err = res_err > res ? res_err : res;
}
errors[m - n0 + 1] = res_err;
}
flag = false;
if ((errors[0] > eps_param) && (errors[1] < eps_param) &&
(errors[2] > eps_param)) {
flag = true;
}
return flag;
}
template
bool check_kern(const int n0, const int lda, const int n,
quadruple *a_ini, int *permute,
const int dim_augkern, const double &eps,
const double &eps_param,
const bool flag_sym,
double *errors,
const bool verbose, FILE *fp);
template
bool check_kern,
double,
complex,
quadruple>(const int n0,
const int lda,
const int n,
complex *a_ini,
int *permute,
const int dim_augkern,
const double &eps,
const double &eps_param,
const bool flag_sym,
double *errors,
const bool verbose, FILE *fp);
#ifndef NO_OCTRUPLE
template
bool check_kern(const int n0, const int lda,
const int n,
octruple *a_ini, int *permute,
const int dim_augkern,
const quadruple &eps,
const quadruple &eps_param,
const bool flag_sym,
quadruple *errors,
const bool verbose, FILE *fp);
template
bool
check_kern,
quadruple,
complex,
octruple>(const int n0,
const int lda,
const int n,
complex *a_ini,
int *permute,
const int dim_augkern,
const quadruple &eps,
const quadruple &eps_param,
const bool flag_sym,
quadruple *errors,
const bool verbose, FILE *fp);
#endif
//
// T may be std::complex of U and W is in higher precision than T
template
U check_matrixerr(const int lda, const int n,
W *a,
const int dim_augkern, const int k,
int *permute,
const U &eps,
const bool flag_sym)
{
U error;
const U Uzero(0.0);
const W one(1.0);
ColumnMatrix nsp2(n, n);
ColumnMatrix nsp3(n, n);
ColumnMatrix nsp4(n, n);
VectorArray v(n);
for (int i = 0; i < (n * n); i++) {
nsp2.addrCoefs()[i] = one;
}
// permutation is given
for (int j = 0; j < k; j++) {
for (int i = 0; i < k; i++) {
const int ij0 = permute[i] + permute[j] * lda;
nsp2(i, j) = W(a[ij0]); // const int ij1 = i + j * n;
}
}
nsp3.copy(nsp2);
nsp4.copy(nsp2);
if (flag_sym) {
full_ldlt(k, nsp3.addrCoefs(), n); // factorization is done in
} // higher accurary
else {
full_ldu(k, nsp3.addrCoefs(), n);
}
full_fwbw_perturb_multi(k, k,
nsp4.addrCoefs(), n,
nsp3.addrCoefs(), nsp2.addrCoefs(),
dim_augkern, eps,
flag_sym);
for (int i = 0; i < k; i++) {
nsp2(i, i) -= one; // nsp2[i + i * n] -= one;
}
error = matrix_infty_norm(k, nsp2.addrCoefs(), n);
return error;
}
template
double check_matrixerr(const int lda, const int n,
quadruple *a,
const int dim_augkern,
const int k, int *permute,
const double &eps,
const bool flag_sym);
template
double check_matrixerr,
double,
complex,
quadruple>(const int lda,
const int n,
complex *a,
const int dim_augkern,
const int k,
int *permute,
const double &eps,
const bool flag_sym);
#ifndef NO_OCTRUPLE
template
quadruple check_matrixerr(const int lda, const int n,
octruple *a,
const int dim_augkern,
const int k, int *permute,
const quadruple &eps,
const bool flag_sym);
template
quadruple
check_matrixerr,
quadruple,
complex,
octruple>(const int lda,
const int n,
complex *a,
const int dim_augkern,
const int k,
int *permute,
const quadruple &eps,
const bool flag_sym);
#endif
//
template
void verify_kernels(const int n0, const int n, const T *a_ini,
const T *a_fact, const int lda,
const double eps, U *errors,
const bool verbose, FILE *fp)
{
const T one(1.0);
const T zero(0.0);
const T none(-1.0);
ColumnMatrix a_p(n, n);
const int n1 = n - n0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n ; j++) {
// const int ij0 = permute[i] + permute[j] * n;
const int ij0 = i + j * lda;
a_p(i, j) = a_ini[ij0]; // const int ij1 = i + j * n;
}
}
// compute [A_11^-1 A_12]
// [ -I ]
VectorArray v(n);
VectorArray w(n);
for (int j = n1; j < n; j++) {
for (int i = 0; i < n1; i++) {
// const int ij0 = permute[i] + permute[j] * n;
const int ij0 = i + j * lda;
v[i] = a_ini[ij0];
}
full_fwbw_part(n1, (T *)a_fact, lda, v.addrCoefs()); //cast : 22 May 2018
for (int i = n1; i < n; i++) {
v[i] = zero;
}
v[j] = none;
blas_gemv(CblasNoTrans, n, n, one, a_p.addrCoefs(), n,
v.addrCoefs(), 1, zero,
w.addrCoefs(), 1);
#if 0
diss_printf(verbose, fp, "%s %d verify_kernels %d\n",
__FILE__, __LINE__, n);
for (int i = 0; i < n; i++) {
diss_printf(verbose, fp, "%d %s %s\n", i, tostring(v[i]).c_str(),
tostring(w[i]).c_str());
}
#endif
errors[j - n1] = blas_l2norm(n, w.addrCoefs(), 1);
}
}
template
void verify_kernels(const int n0, const int n,
const double *a_ini,
const double *a_fact,
const int lda,
const double eps,
double *errors,
const bool verbose, FILE *fp);
template
void verify_kernels, double>(const int n0, const int n,
const complex *a_ini,
const complex *a_fact,
const int lda,
const double eps,
double *errors,
const bool verbose, FILE *fp);
template
void verify_kernels(const int n0, const int n,
const quadruple *a_ini,
const quadruple *a_fact,
const int lda,
const double eps,
quadruple *errors,
const bool verbose, FILE *fp);
template
void verify_kernels,
quadruple>(const int n0, const int n,
const complex *a_ini,
const complex *a_fact,
const int lda,
const double eps,
quadruple *errors,
const bool verbose, FILE *fp);
//
template
void HouseholderVector_complex(int n, T *x, T *v, T *gamma)
{
const U zero(0.0);
const U one(1.0);
const U two(2.0);
const U onehalf(1.5);
const T czero(zero, zero);
const T cone(one, zero);
const T ctwo(two, zero);
const U pi(M_PI);
U s = blas_l2norm2((n - 1), &x[1], 1);
v[0] = cone;
for (int i = 1; i < n; i++) {
v[i] = x[i];
}
if (s == zero) {
*gamma = czero;
}
else {
// U x0arg = std::arg(x[0]);
U x0arg = atan2(x[0].imag(), x[0].real());
const T alpha = complex(cos(x0arg), sin(x0arg));
U xabs = sqrt(x[0].real() * x[0].real() +
x[0].imag() * x[0].imag());
if ((x0arg >= pi / two) && (x0arg < pi * onehalf)) {
v[0] = alpha * (xabs + sqrt(s));
}
else {
v[0] = alpha * (-s) / (xabs + sqrt(s));
}
const U v0r(v[0].real());
const U v0i(v[0].imag());
const U v0sq = v0r * v0r + v0i * v0i;
*gamma = ctwo * v0sq / (s + v0sq);
T z = one / v[0];
for (int i = 0; i < n; i++) {
v[i] *= z;
}
}
}
template
void HouseholderVector_complex, double>(int n,
complex *x,
complex *v,
complex *gamma);
template
void HouseholderVector_complex,
quadruple>(int n,
complex *x,
complex *v,
complex *gamma);
template
void HouseholderVector_complex, float>(int n,
complex *x,
complex *v,
complex *gamma);
//
template
void HouseholderVector(int n, T *x, T *v, T *gamma)
{
const T one(1.0);
const T zero(0.0);
const T two(2.0);
const T s = blas_l2norm2((n - 1), &x[1], 1);
v[0] = one;
for (int i = 1; i < n; i++) {
v[i] = x[i];
}
if (s == zero) {
*gamma = zero;
}
else {
T z = sqrt(x[0] * x[0] + s);
if (x[0] <= zero) {
v[0] = x[0] - z;
}
else {
v[0] = (-s) / (x[0] + z);
}
*gamma = two * v[0] * v[0] / (s + v[0] * v[0]);
z = one / v[0];
for (int i = 0; i < n; i++) {
v[i] *= z;
}
}
}
template<>
void HouseholderVector >(int n,
complex *x,
complex *v,
complex *gamma)
{
HouseholderVector_complex, double>(n, x, v, gamma);
}
template<>
void HouseholderVector >(int n,
complex *x,
complex *v,
complex *gamma)
{
HouseholderVector_complex, quadruple>(n, x, v, gamma);
}
template<>
void HouseholderVector >(int n,
complex *x,
complex *v,
complex *gamma)
{
HouseholderVector_complex, octruple>(n, x, v, gamma);
}
template<>
void HouseholderVector >(int n,
complex *x,
complex *v,
complex *gamma)
{
HouseholderVector_complex, float>(n, x, v, gamma);
}
template
void HouseholderVector(int n, double *x, double *v, double *gamma);
template
void HouseholderVector(int n, quadruple *x, quadruple *v,
quadruple *gamma);
template
void HouseholderVector(int n, float *x, float *v, float *gamma);
#if 0
template
void HouseholderVector >(int n,
complex *x,
complex *v,
complex *gamma);
template
void HouseholderVector >(int n,
complex *x,
complex *v,
complex *gamma);
#endif
//
template
void HouseholderReflection(int n, T *a, int lda, T *v, T *w, const T &gamma)
{
const T one(1.0);
const T zero(0.0);
blas_gemv(CblasConjTrans, n, n, one, a, lda, v, 1, zero, w, 1);
T ngamma = (-gamma);
blas_gerc(n, n, ngamma, v, 1, w, 1, a, lda);
}
template
void HouseholderReflection(int n, double *a, int lda, double *v,
double *w, const double &gamma);
template
void HouseholderReflection >(int n, complex *a, int lda,
complex *v,
complex *w,
const complex &gamma);
template
void HouseholderReflection(int n, quadruple *a, int lda,
quadruple *v,
quadruple *w, const quadruple &gamma);
template
void
HouseholderReflection >(int n,
complex *a, int lda,
complex *v,
complex *w,
const complex &gamma);
template
void HouseholderReflection(int n, float *a, int lda, float *v,
float *w, const float &gamma);
template
void HouseholderReflection >(int n, complex *a, int lda,
complex *v,
complex *w,
const complex &gamma);
//
// T may be complex of U
template
int hqr_pivot(const int n, T *a, int *permute)
{
const T Tzero(0.0);
const U Uzero(0.0);
int n0, k;
VectorArray cc(n);
VectorArray col(n);
VectorArray v(n);
VectorArray w(n);
for (int i = 0 ; i < n; i++) {
cc[i] = blas_l2norm2(n, &a[i * n], 1); // norm2 returns double value
permute[i] = i;
}
k = 0;
{
U tmp(0.0);
for (int i = 0; i < n; i++) {
if (cc[i] > tmp) {
tmp = cc[i];
k = i; // find the first entry that attains the maximum value
}
} // loop : i
}
n0 = 0;
for (int m = 0; m < n; m++) {
if (k > m) { // swap k-th and m-th columns of A[]
int kk = permute[m];
permute[m] = permute[k];
permute[k] = kk;
for (int i = 0; i < n; i++) {
col[i] = a[i + m * n];
}
for (int i = 0; i < n; i++) {
a[i + m * n] = a[i + k * n];
}
for (int i = 0; i < n; i++) {
a[i + k * n] = col[i];
}
U c = cc[m];
cc[m] = cc[k];
cc[k] = c;
} // if (k > m)
int nm = n - m;
T gamma;
HouseholderVector(nm, &a[m + m * n], v.addrCoefs(), &gamma);
HouseholderReflection(nm, &a[m + m * n], n,
v.addrCoefs(), w.addrCoefs(), gamma);
for (int i = (m + 1); i < n; i++) {
a[i + m * n] = Tzero; // = v[i] : to keep Householder matrix
}
for (int i = (m + 1); i < n; i++) {
cc[i] = blas_l2norm2((n - m - 1), &a[m + 1 + i * n], 1);
}
U tt(0.0);
for (int i = (m + 1); i < n; i++) {
if (cc[i] > tt) {
tt = cc[i];
k = i; // find the first entry that attains the maximum value
}
} // loop : i
if (tt == Uzero) {
n0 = n - (m + 1);
break;
}
} // loop : m
return (n - n0);
}
template
int hqr_pivot(const int n, double *a, int *permute);
template
int hqr_pivot, double>(const int n, complex *a,
int *permute);
template
int hqr_pivot(const int n, quadruple *a, int *permute);
template
int hqr_pivot, quadruple>(const int n,
complex *a,
int *permute);
template
int hqr_pivot(const int n, float *a, int *permute);
template
int hqr_pivot, float>(const int n, complex *a,
int *permute);
//
template
bool ComputeDimKernel_(int *n0, bool *flag_unsym_permute,
const T *a_, const int n,
const bool sym_flag,
const int dim_augkern,
const U eps_machine, // for perturbation
const double eps_piv,
const bool verbose,
FILE *fp)
{
const W zero(0.0);
const Y Yzero(0.0);
const Y Yone(1.0);
const U Uzero(0.0);
Y Yeps_machine;
Yeps_machine = conv_prec(eps_machine);
// dimension of the image of the matrix a is at least one
int nn0, n1, n2;
int n_dim = n + 1;
int *permute = new int[n_dim];
ColumnMatrix aq0(n_dim, n_dim);
ColumnMatrix ad0(n, n);
ColumnMatrix a1(n_dim, n_dim);
ColumnMatrix aq_fact(n_dim, n_dim);
ColumnMatrix ad_fact(n, n);
VectorArray aa_diag(n_dim);
// VectorArray diag_scale(n_dim);
VectorArray rr(n_dim - 1);
int *permute_d = new int[n_dim];
int *permute_q = new int[n_dim];
int *permute_right = new int[n_dim];
int *permute_left = new int[n_dim];
bool flag_tmp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a1(i, j) = conv_prec(a_[i + j * n]);
}
}
if (sym_flag) {
flag_tmp = false;
for (int i = 0; i < n; i++) {
permute_left[i] = permute_right[i] = i;
}
}
else {
double pivot = 1.0;
double fop;
double epspiv = todouble(eps_machine);
ldu_full_permute(&nn0, 0, n, a1.addrCoefs(), n_dim, &pivot,
permute_right, permute_left,
epspiv, &fop);
flag_tmp = false;
for (int i = 0; i < n; i++) {
if (permute_left[i] != permute_right[i]) {
flag_tmp = true;
break;
}
}
}
diss_printf(verbose, fp, "%s %d : %s pivots\n",
__FILE__, __LINE__,
flag_tmp ? "full" : "symmetric ");
for (int i = 0; i < n; i++) {
diss_printf(verbose, fp, "%d : %d %d %s\n",
i, permute_left[i], permute_right[i],
tostring(a1(i, i)).c_str());
// tostring(tolower(diag_scale[i])).c_str());
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
a1(i, j) = conv_prec(a_[permute_left[i] + permute_right[j] * n]);
}
}
diss_printf(verbose, fp, "%s %d : permuted Schur complement %d\n",
__FILE__, __LINE__, n);
for (int i = 0; i < n; i++) {
diss_printf(verbose, fp, "%d ", i);
for (int j = 0; j < n; j++) {
diss_printf(verbose, fp, "%s ",
tostring(conv_prec(a1(i, j))).c_str());
}
diss_printf(verbose, fp, "\n");
}
for (int i = 0; i < n; i++) {
W tmp = zero;
for (int j = 0; j < n; j++) {
tmp += a1(i, j) + (random_bool() ? Yeps_machine : Yzero);
}
a1(i, n) = tmp;
a1(n, n) += tmp + (random_bool() ? Yeps_machine : Yzero);
}
for (int j = 0; j < n; j++) {
W tmp = zero;
for (int i = 0; i < n; i++) {
tmp += a1(i, j) + (random_bool() ? Yeps_machine : Yzero);
}
a1(n, j) = tmp;
}
// column and row of inflated matrix are scaled
Y diag_scalen = sqrt(Yone / blas_abs(a1(n, n)));
for (int i = 0; i < n; i++) {
a1(i, n) *= diag_scalen;
a1(n, i) *= diag_scalen;
}
a1(n, n) *= (diag_scalen * diag_scalen);
diss_printf(verbose, fp, "%s %d : the original Schur complement %d\n",
__FILE__, __LINE__, n);
for (int i = 0; i < n; i++) {
diss_printf(verbose, fp, "%d ", i);
for (int j = 0; j < n; j++) {
diss_printf(verbose, fp, "%s ",
tostring(conv_prec(a_[i + j * n])).c_str());
}
diss_printf(verbose, fp, "\n");
}
diss_printf(verbose, fp, "%s %d : the scaled last Schur complement %d\n",
__FILE__, __LINE__, n_dim);
for (int i = 0; i < n_dim; i++) {
diss_printf(verbose, fp, "%d ", i);
for (int j = 0; j < n_dim; j++) {
diss_printf(verbose, fp, "%s ",
tostring(conv_prec(a1(i,j))).c_str());
}
diss_printf(verbose, fp, "\n");
}
aq0.copy(a1);
aq_fact.copy(a1);
n1 = hqr_pivot(n_dim, aq0.addrCoefs(), permute);
diss_printf(verbose, fp,
"%s %d dimension of the image deteced by d_hqr_pivot() is %d\n",
__FILE__, __LINE__, n1);
diss_printf(verbose, fp, "%s %d QR\n", __FILE__, __LINE__);
for (int i = 0; i < n_dim; i++) {
diss_printf(verbose, fp, "%d : %d ", i, permute[i]);
for (int j = 0; j < n_dim; j++) {
diss_printf(verbose, fp, "%s ",
tostring(conv_prec(aq0(i, j))).c_str());
}
diss_printf(verbose, fp, "\n");
}
for (int i = 0; i < n1; i++) {
aa_diag[i] = aq0(i, i);
}
list pos_gap;
vector kernel_dim;
pos_gap.push_back(dim_augkern);
for (int i = 0; i < (n1 - 1); i++) {
rr[i] = todouble(blas_abs(aa_diag[i + 1] / aa_diag[i]));
}
// find largest gap inside of invertible part
double aug_diff = 1.0;
for (int i = 0; i < (dim_augkern - 1); i++) {
if (aug_diff > rr[i]) {
aug_diff = rr[i];
}
}
diss_printf(verbose, fp, "%s %d : aug_diff = %s esp = %.12e\n",
__FILE__, __LINE__,
tostring(aug_diff).c_str(), eps_piv);
for (int i = (dim_augkern - 1); i < (n1 - 1); i++) {
if (rr[i] < (aug_diff * eps_piv)) {
diss_printf(verbose, fp, "rr[%d] : %s\n",
i, tostring(rr[i]).c_str());
pos_gap.push_back(i + 1);
}
}
const bool flag_perturb =
((rr[dim_augkern - 1] < aug_diff)
&& (blas_abs(aa_diag[n1 - 1]) > Yeps_machine * Y(eps_piv)));
const U eps_perturb = flag_perturb ? eps_machine : Uzero;
diss_printf(verbose, fp, "%s %d : rr[%d] = %s => perturb = %s %s\n",
__FILE__, __LINE__,
(dim_augkern - 1),
tostring(rr[dim_augkern - 1]).c_str(),
tostring(eps_perturb).c_str(),
tostring(blas_abs(aa_diag[n1 - 1])).c_str()
);
int n_dim1;
if (flag_perturb) { // condition number of the invertible part is moderate
n2 = n1; // and the diagonal entry becomes etreamly small
// n1 may be less than n_dim when a diagnal of QR == 0
for (int i = 0; i < (n1 - 1); i++) {
if (rr[i] < (todouble(eps_machine) / sqrt(eps_piv))) {
n2 = i + 1;
break;
}
}
n_dim1 = n2 > dim_augkern ? n2 : n_dim;
pos_gap.push_back(n2 - 1); // matrix being inflated
}
else {
n_dim1 = n_dim;
pos_gap.push_back(n); // matrix being inflated : n = n_dim - 1
}
rr.free();
pos_gap.sort();
pos_gap.unique();
for (list::const_iterator it = pos_gap.begin(); it != pos_gap.end();
++it) {
kernel_dim.push_back(n_dim1 - (*it));
}
diss_printf(verbose, fp, "%s %d : kernel_dim = %d : ",
__FILE__, __LINE__, (int)kernel_dim.size());
for (vector::const_iterator it = kernel_dim.begin();
it != kernel_dim.end();
++it) {
diss_printf(verbose, fp, "%d ", *it);
}
diss_printf(verbose, fp, "\n");
int flag;
flag = VerifyDimKernel(&nn0, permute_q,
n_dim1, aq_fact.addrCoefs(), kernel_dim,
sym_flag, dim_augkern, eps_perturb,
verbose, fp);
if (flag == false) {
nn0 = 1; // iflated matrix is generated as singular
}
// nn0 += (n_dim - n2) - 1;
// nn0--; // detection of kernel is done for dim_augkern > 0 and at least
// if (nn0 > 0) {
{
const double eps_machine_double = todouble(eps_machine);
U *errors_d = new U[nn0 + 1];
list nnn;
if (nn0 > 2) {
nnn.push_back(nn0 - 2);
}
nnn.push_back(nn0 - 1); //
nnn.push_back(nn0);
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
ad_fact(i, j) = a_[i + j * n];
}
}
{
double pivot_ref = 0.0;
for (int i = 0; i < n ; i++) {
double tmp = blas_abs(a_[i + i * n]);
pivot_ref = pivot_ref > tmp ? pivot_ref : tmp;
}
int nnn0;
double fop;
if (sym_flag) {
full_ldlt_permute(&nnn0, 0, n, ad_fact.addrCoefs(), n,
&pivot_ref, permute_d, eps_machine_double,
&fop);
}
else {
full_ldu_permute(&nnn0, 0, n, ad_fact.addrCoefs(), n,
&pivot_ref, permute_d, eps_machine_double,
&fop);
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
ad0(i, j) = a_[permute_d[i] + permute_d[j] * n];
}
}
diss_printf(verbose, fp, "%s %d : verify errors : size = %d : ",
__FILE__, __LINE__, nnn.size());
for (list::const_iterator it = nnn.begin(); it != nnn.end();
++it) {
diss_printf(verbose, fp, "%d ", (*it));
}
diss_printf(verbose, fp, "\n");
for (list::const_iterator it = nnn.begin(); it != nnn.end();
++it) {
const int nn = (*it);
if (nn > 0) {
verify_kernels(nn, n, ad0.addrCoefs(), ad_fact.addrCoefs(),
n,
eps_machine_double, errors_d,
verbose, fp);
diss_printf(verbose, fp, "errors of %d kernels\n", nn);
for (int i = 0; i < nn; i++) {
diss_printf(verbose, fp,
"%d : %s\n", i, tostring(errors_d[i]).c_str());
}
}
}
if (flag_tmp) {
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
ad_fact(i, j) = a_[permute_left[i] + permute_right[j] * n];
}
}
{
double pivot_ref = 0.0;
for (int i = 0; i < n ; i++) {
double tmp = blas_abs(a_[i + i * n]);
pivot_ref = pivot_ref > tmp ? pivot_ref : tmp;
}
int nnn0;
double fop;
if (sym_flag) {
full_ldlt_permute(&nnn0, 0, n, ad_fact.addrCoefs(), n,
&pivot_ref, permute_d, eps_machine_double,
&fop);
}
else {
full_ldu_permute(&nnn0, 0, n, ad_fact.addrCoefs(), n,
&pivot_ref, permute_d, eps_machine_double,
&fop);
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
ad0(i, j) = a_[permute_d[permute_left[i]] + permute_d[permute_right[j]] * n];
}
}
diss_printf(verbose, fp, "%s %d : verify errors : size = %d : ",
__FILE__, __LINE__, nnn.size());
for (list::const_iterator it = nnn.begin(); it != nnn.end();
++it) {
diss_printf(verbose, fp, "%d ", (*it));
}
diss_printf(verbose, fp, "\n");
for (list::const_iterator it = nnn.begin(); it != nnn.end();
++it) {
const int nn = (*it);
if (nn > 0) {
verify_kernels(nn, n, ad0.addrCoefs(), ad_fact.addrCoefs(), n,
eps_machine_double, errors_d,
verbose, fp);
diss_printf(verbose, fp, "errors of %d kernels\n", nn);
for (int i = 0; i < nn; i++) {
diss_printf(verbose, fp,
"%d : %s\n", i, tostring(errors_d[i]).c_str());
}
}
}
} // if (flag_tmp)
// nnn.clear();
Y *errors_q = new Y[nn0 + 1];
for (int j = 0; j < n_dim; j++) {
for (int i = 0; i < n_dim; i++) {
aq0(i, j) = a1(permute_q[i], permute_q[j]);
}
}
for (list::const_iterator it = nnn.begin(); it != nnn.end();
++it) {
const int nn = (*it) + 1;
verify_kernels(nn, n_dim,
aq0.addrCoefs(), aq_fact.addrCoefs(), n_dim,
eps_machine_double, errors_q,
verbose, fp);
diss_printf(verbose, fp, "errors of %d kernels\n", nn);
for (int i = 0; i < nn; i++) {
diss_printf(verbose, fp,
"%d : %s\n", i,
tostring(errors_q[i]).c_str());
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
aq_fact(i, j) = conv_prec(a_[i + j * n]);
}
}
{
double pivot_ref = 0.0;
for (int i = 0; i < n ; i++) {
double tmp = blas_abs(a_[i + i * n]);
pivot_ref = pivot_ref > tmp ? pivot_ref : tmp;
}
int nnn0;
double fop;
if (sym_flag) {
full_ldlt_permute(&nnn0, 0, n, aq_fact.addrCoefs(), n_dim,
&pivot_ref, permute_q, eps_machine_double,
&fop);
}
else {
full_ldu_permute(&nnn0, 0, n, aq_fact.addrCoefs(), n_dim,
&pivot_ref, permute_q, eps_machine_double,
&fop);
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
aq0(i, j) = conv_prec(a_[permute_q[i] + permute_q[j] * n]);
}
}
diss_printf(verbose, fp, "%s %d : verify errors : size = %d : ",
__FILE__, __LINE__, nnn.size());
for (list::const_iterator it = nnn.begin(); it != nnn.end();
++it) {
diss_printf(verbose, fp, "%d ", (*it));
}
diss_printf(verbose, fp, "\n");
for (list::const_iterator it = nnn.begin(); it != nnn.end();
++it) {
const int nn = (*it);
if (nn > 0) {
verify_kernels(nn, n,
aq0.addrCoefs(), aq_fact.addrCoefs(), n_dim,
eps_machine_double, errors_q,
verbose, fp);
diss_printf(verbose, fp, "errors of %d kernels\n", nn);
for (int i = 0; i < nn; i++) {
diss_printf(verbose, fp,
"%d : %s\n", i, tostring(errors_q[i]).c_str());
}
}
}
nnn.clear();
delete [] errors_q;
delete [] errors_d;
} // if (nn0 > 0)
delete [] permute;
delete [] permute_d;
delete [] permute_q;
delete [] permute_left;
delete [] permute_right;
*n0 = nn0 + (n_dim - n_dim1) - 1;
diss_printf(verbose, fp,
"%s %d : dimension of the kernel is %d\n",
__FILE__, __LINE__, *n0);
*flag_unsym_permute = flag_tmp;
return flag;
}
template
bool ComputeDimKernel_(int *n0, bool *flag_unsym_permute,
const double *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const double eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp);
template
bool ComputeDimKernel_,
double,
complex,
quadruple>(int *n0, bool *flag_unsym_permute,
const complex *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const double eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp);
template
bool ComputeDimKernel_(int *n0, bool *flag_unsym_permute,
const quadruple *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const quadruple eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp);
template
bool ComputeDimKernel_,
quadruple,
complex,
octruple>(int *n0, bool *flag_unsym_permute,
const complex *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const quadruple eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp);
template
bool ComputeDimKernel(int *n0, bool *flag_unsym_permute,
const T *a_, const int n,
const bool sym_flag,
const int dim_augkern,
const U eps_machine, // for perturbation
const double eps_piv,
const bool verbose,
FILE *fp)
{
fprintf(stderr, "%s %d : specialized template not implemented\n",
__FILE__, __LINE__);
}
template<>
bool ComputeDimKernel(int *n0, bool *flag_unsym_permute,
const double *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const double eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp)
{
return ComputeDimKernel_(n0, flag_unsym_permute, a_, n,
sym_flag, dim_augkern,
eps_machine, eps_piv,
verbose, fp);
}
template<>
bool ComputeDimKernel,
double>(int *n0, bool *flag_unsym_permute,
const complex *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const double eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp)
{
return ComputeDimKernel_,
double,
complex,
quadruple>(n0, flag_unsym_permute, a_, n,
sym_flag, dim_augkern,
eps_machine, eps_piv,
verbose, fp);
}
template<>
bool ComputeDimKernel(int *n0, bool *flag_unsym_permute,
const quadruple *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const quadruple eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp)
{
return ComputeDimKernel_(n0, flag_unsym_permute, a_, n,
sym_flag, dim_augkern,
eps_machine, eps_piv,
verbose, fp);
}
template<>
bool ComputeDimKernel,
quadruple>(int *n0, bool *flag_unsym_permute,
const complex *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const quadruple eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp)
{
return ComputeDimKernel_,
quadruple,
complex,
octruple>(n0, flag_unsym_permute, a_, n,
sym_flag, dim_augkern,
eps_machine, eps_piv,
verbose, fp);
}
template<>
bool ComputeDimKernel(int *n0, bool *flag_unsym_permute,
const float *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const float eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp)
{
return ComputeDimKernel_(n0, flag_unsym_permute, a_, n,
sym_flag, dim_augkern,
eps_machine, eps_piv,
verbose, fp);
}
template<>
bool ComputeDimKernel,
float>(int *n0, bool *flag_unsym_permute,
const complex *a_,
const int n,
const bool sym_flag,
const int dim_augkern,
const float eps_machine,
const double eps_piv,
const bool verbose,
FILE *fp)
{
return ComputeDimKernel_,
float,
complex,
double>(n0, flag_unsym_permute, a_, n,
sym_flag, dim_augkern,
eps_machine, eps_piv,
verbose, fp);
}
//
template
bool VerifyDimKernel(int *nn0_,
int *permute_q,
int n_dim, W* a_fact,
vector &kernel_dim,
const bool sym_flag,
const int dim_augkern,
const U eps_machine,
const bool verbose,
FILE *fp)
{
U Uzero(0.0);
U Uone(1.0);
int nn, nn0;
int k;
double pivot_ref, pivot_ref_q;
// int *permute_q = new int[n_dim];
ColumnMatrix a2(n_dim, n_dim);
U *errors = new U[6];
blas_copy