/*! \file SparseMatrix.cpp
\brief Sparse matrix definition
\author Xavier Juvigny, ONERA
\date Jan. 25th 2005
\modification allocation of array by STL vector class
\author Atsushi Suzuki, Laboratoire Jacques-Louis Lions
\date Jun. 11th 2013
\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 "Algebra/SparseMatrix.hpp"
#include "Algebra/VectorArray.hpp"
#include "Compiler/OptionCompiler.hpp"
#include "Compiler/arithmetic.hpp"
#include "Driver/DissectionDefault.hpp" // for definition of scaling option
#include
#include
#include
inline
double SpMAX(double a, double b)
{
return (a > b ? a : b);
}
inline
quadruple SpMAX(quadruple a, quadruple b)
{
return (a > b ? a : b);
}
template void
normalize(const int type, const T* coefs0, SparseMatrix *ptDA, U* u)
{
const T zero(0.0);
const T one(1.0);
const U Uone(1.0);
const U Uzero(0.0);
const int n = ptDA->dimension();
VectorArray v(n); // Z* v = new Z[n];
VectorArray d(n); // Z* d = new Z[n];
int *ptUnsymRows, *indUnsymCols, *indVals;
if (ptDA->isSymmetric() && (type == KKT_SCALING)) {
const int nnz = ptDA->nnz();
if (ptDA->isWhole()) {
ptUnsymRows = ptDA->getRows();
indUnsymCols = ptDA->getIndCols();
indVals = new int[nnz];
for (int i = 0; i < nnz; i++) {
indVals[i] = i;
}
}
else {
const int nnz0 = nnz * 2 - n;
ptUnsymRows = new int[n + 1];
indUnsymCols = new int[nnz0]; // diagonal entries exits though
indVals = new int[nnz0]; // coeficient equals to zero
// only used as extend symmetric symbolic structure to unsymmetric
int nnz1;
nnz1 = CSR_sym2unsym(ptUnsymRows, indUnsymCols, indVals, ptDA->getRows(),
ptDA->getIndCols(),
n, ptDA->isUpper());
if (nnz1 != nnz0) {
fprintf(stderr,
"%s %d : symmetric matrix has no diagonal entry %d != %d\n",
__FILE__, __LINE__, nnz0, nnz1);
exit(-1);
}
}
}
for (int i = 0; i < n; i++) {
d[i] = Uzero;
u[i] = Uzero;
v[i] = Uzero;
}
for (int i = 0; i < n; i++) {
for (unsigned k = ptDA->getRows()[i]; k < ptDA->getRows()[i + 1]; k++) {
int j = ptDA->getIndCols()[k];
if (i == j) {
d[i] = blas_abs(coefs0[k]);
}
}
}
// 23 Jun.2011 Atsushi
// u[i] = |a(i, i)|, v[i] = max_{k}{|a(i,k)|,|a(k,j)|}
if (ptDA->isSymmetric() && (!ptDA->isWhole())) {
for (int i = 0; i < n; i++) {
u[i] = blas_abs(coefs0[ptDA->getRows()[i]]);
v[i] = SpMAX(v[i], u[i]);
for (int k = (ptDA->getRows()[i] + 1); k < ptDA->getRows()[i + 1]; k++) {
int j = ptDA->getIndCols()[k];
U acoef = blas_abs(coefs0[k]);
v[i] = SpMAX(v[i], acoef);
v[j] = SpMAX(v[j], acoef);
}
}
}
else {
for (int i = 0; i < n; i++) {
for (int k = ptDA->getRows()[i]; k < ptDA->getRows()[i + 1]; k++) {
int j = ptDA->getIndCols()[k];
if (j == i) {
u[i] = blas_abs(coefs0[k]);
v[i] = SpMAX(v[i],u[i]);
}
else {
U acoef = blas_abs(coefs0[k]);
v[i] = SpMAX(v[i], acoef);
v[j] = SpMAX(v[j], acoef);
}
}
}
}
T alower, aupper, adiag;
switch(type) {
case DIAGONAL_SCALING:
for (int i = 0; i < n; i++) {
u[i] = ((u[i] != Uzero) ? sqrt(Uone / u[i]) :
((v[i] != Uzero) ? sqrt(Uone / v[i]) : Uone));
}
break;
case KKT_SCALING:
if (ptDA->isSymmetric() && (!ptDA->isWhole())) {
for (int i = 0 ; i < n; i++) {
if (d[i] != Uzero) {
u[i] = sqrt(Uone / u[i]);
}
else {
T xtmp = zero;
for (int m = ptUnsymRows[i]; m < ptUnsymRows[i + 1]; m++) {
const int j = indUnsymCols[m];
alower = coefs0[indVals[m]];
int flag = 0;
for (int n = ptUnsymRows[j]; n < ptUnsymRows[j + 1]; n++) {
const int k = indUnsymCols[n];
if (k == j) {
adiag = coefs0[indVals[n]];
if (adiag != zero) {
flag++;
}
else {
continue;
}
}
if (k == i) {
aupper = coefs0[indVals[n]];
flag++;
}
if (flag == 2) {
break;
}
} // loop : n
if (flag == 2) {
xtmp += alower * aupper / adiag;
}
} // loop : m
u[i] = Uone / sqrt(blas_abs(xtmp));
} // if (d[i] != zero)
} // loop : i
} // if (_isSymmetric && (!_isWhole))
else {
for (int i = 0 ; i < n; i++) {
if (d[i] != Uzero) {
u[i] = sqrt(Uone / u[i]);
}
else {
T xtmp = zero;
for (int m = ptDA->getRows()[i]; m < ptDA->getRows()[i + 1]; m++) {
const int j = ptDA->getIndCols()[m];
alower = coefs0[m];
int flag = 0;
for (int n = ptDA->getRows()[j]; n < ptDA->getRows()[j + 1]; n++) {
const int k = ptDA->getIndCols()[n];
if (k == j) {
adiag = coefs0[n];
if (adiag != zero) {
flag++;
}
else {
continue;
}
}
if (k == i) {
aupper = coefs0[n];
flag++;
}
if (flag == 2) {
break;
}
} // loop : n
if (flag == 2) {
xtmp += alower * aupper / adiag;
}
} // loop : m
u[i] = Uone / sqrt(blas_abs(xtmp));
} // if (d[i] != zero)
} // loop : i
} // if (_isSymmetric && (!_isWhole))
break;
default:
for (int i = 0; i < n; i++) {
u[i] = Uone;
}
break;
} // witch (type)
// Scaling
switch(type) {
case NO_SCALING:
for (int i = 0; i < ptDA->getRows()[n]; i++) {
ptDA->getCoef()[i] = coefs0[i];
}
break;
case DIAGONAL_SCALING:
case KKT_SCALING:
for ( int i = 0; i < n; i++) {
for (int k = ptDA->getRows()[i]; k < ptDA->getRows()[i+1]; k++) {
int j = ptDA->getIndCols()[k];
ptDA->getCoef()[k] = coefs0[k] * u[i] *u[j];
}
}
break;
}
// delete [] v;
// delete [] d;
if (ptDA->isSymmetric() && (type == KKT_SCALING)) {
if (!ptDA->isWhole()) {
delete [] ptUnsymRows;
delete [] indUnsymCols;
}
delete [] indVals;
}
}
template void
normalize(const int type, const double *coefs0,
SparseMatrix *ptDA, double *u);
template void
normalize(const int type,
const quadruple *coefs0,
SparseMatrix *ptDA,
quadruple *u);
template void
normalize, double>
(const int type, const complex *coefs0,
SparseMatrix > *ptDA, double *u);
template void
normalize, quadruple>
(const int type, const complex *coefs0,
SparseMatrix > *ptDA, quadruple *u);
template void
normalize(const int type, const float *coefs0,
SparseMatrix *ptDA, float *u);
template void
normalize, float>
(const int type, const complex *coefs0,
SparseMatrix > *ptDA, float *u);
//
template void
SparseMatrix::extractSquareMatrix(T* DSsingCoefs, vector &singVal)
{
const T zero(0.0);
const int nsing = singVal.size();
if (_isSymmetric && (!_isWhole)) {
if (_isUpper) {
for (int i = 0; i < nsing; i++) {
for (int j = i; j < nsing; j++) {
DSsingCoefs[i + j * nsing] = 0.0;
const int icol = singVal[i];
int itmp = icol;
for (int it = ptRow(icol); it < ptRow(icol + 1); it++) {
itmp = indCol(it);
if (itmp == singVal[j]) {
DSsingCoefs[i + j * nsing] = Coef(it);
}
}
}
//symmetrize
for (int j = i + 1; j < nsing; j++) {
DSsingCoefs[j + i * nsing] = DSsingCoefs[i + j * nsing];
}
}
} // if (isUpper())
else {
for (int i = 0; i < nsing; i++) {
for (int j = 0; j <= i; j++) {
DSsingCoefs[i + j * nsing] = zero;
const int icol = singVal[i];
int itmp = icol;
for (int it = ptRow(icol); it < ptRow(icol + 1); it++) {
itmp = indCol(it);
if (itmp == singVal[j]) {
DSsingCoefs[i + j * nsing] = Coef(it);
}
}
}
//symmetrize
for (int j = 0; j < i; j++) {
DSsingCoefs[j + i * nsing] = DSsingCoefs[i + j * nsing];
}
}
} // if (isUpper())
}
else {
//
for (int i = 0; i < nsing; i++) {
for (int j = 0; j < nsing; j++) {
DSsingCoefs[i + j * nsing] = zero;
const int icol = singVal[i];
for (int it = ptRow(icol); it != ptRow(icol + 1); it++) {
if (indCol(it) == singVal[j]) {
DSsingCoefs[i + j * nsing] = Coef(it);
break;
}
}
}
}
}
}
template void
SparseMatrix::extractSquareMatrix(double* DSsingCoefs,
vector &singVal);
template void
SparseMatrix::extractSquareMatrix(quadruple* DSsingCoefs,
vector &singVal);
template void
SparseMatrix >::extractSquareMatrix(complex* DSsingCoefs,
vector &singVal);
template void
SparseMatrix >::extractSquareMatrix(complex* DSsingCoefs,
vector &singVal);
template void
SparseMatrix::extractSquareMatrix(float* DSsingCoefs,
vector &singVal);
template void
SparseMatrix >::extractSquareMatrix(complex* DSsingCoefs,
vector &singVal);
//
template
void SparseMatrix::prod(const T *u, T *v) const
{
const T zero(0.0);
for (int i = 0; i < dimension(); i++) {
v[i] = zero;
}
if (_isSymmetric && (!_isWhole)) {
for(int i = 0; i < dimension(); i++) {
// assumption data structure
// _indCols[k] < _indCols[k + 1]
// _indCols[_ptRows[i]] = i for _isUpper == true
// _indCols[_ptRows[i + 1] - 1] = i for _isUpper == false
int ibegin, iend;
if (_isUpper) {
ibegin = _ptRows[i] + 1;
iend = _ptRows[i + 1];
}
else {
ibegin = _ptRows[i];
iend = _ptRows[i + 1] - 1;
}
for (int k = ibegin; k < iend; k++) {
const int icol = _indCols[k];
v[i] += _coefs[k] * u[icol];
v[icol] += _coefs[k] * u[i];
}
const int k = _isUpper ? _ptRows[i] : (_ptRows[i + 1] - 1); // diagonal
v[i] += _coefs[k] * u[_indCols[k]];
} // loop : i
}
else {
for(int i = 0; i < dimension(); i++) {
for (int k = _ptRows[i]; k < _ptRows[i + 1]; k++) {
v[i] += _coefs[k] * u[_indCols[k]];
}
}
}
}
template
void SparseMatrix::prod(const double *u, double *v) const;
template
void SparseMatrix::prod(const quadruple *u, quadruple *v) const;
template
void SparseMatrix >::prod(const complex *u,
complex *v) const;
template
void SparseMatrix >::prod(const complex *u,
complex *v) const;
template
void SparseMatrix::prod(const float *u, float *v) const;
template
void SparseMatrix >::prod(const complex *u,
complex *v) const;
//
template
void SparseMatrix::prodt(const T *u, T *v ) const
{
const T zero(0.0);
for (int i = 0; i < dimension(); i++) {
v[i] = zero;
}
for(int i = 0; i < dimension(); i++) {
for (int k = _ptRows[i]; k < _ptRows[i + 1]; k++) {
v[_indCols[k]] += _coefs[k]*u[i];
}
}
}
template
void SparseMatrix::prodt(const double *u, double *v) const;
template
void SparseMatrix::prodt(const quadruple *u, quadruple *v) const;
template
void SparseMatrix >::prodt(const complex *u,
complex *v) const;
template
void SparseMatrix >::prodt(const complex *u,
complex *v) const;
template
void SparseMatrix::prodt(const float *u, float *v) const;
template
void SparseMatrix >::prodt(const complex *u,
complex *v) const;
//
template
SparseMatrix* SparseMatrix::PartialCopyCSR(vector &permute,
const int n,
bool transposed)
{
vector dist_ptRows;
dist_ptRows.resize(n + 1);
int *source_ptRows = getRows(); //&source->beginRows()[0];
SparseMatrix *dist;
if (_isSymmetric && !(_isWhole)) {
int *width = new int[n];
for (int i = 0; i < n; i++) {
width[i] = source_ptRows[permute[i] + 1] - source_ptRows[permute[i]];
}
for (int i = 0; i < dimension(); i++) {
for (int it = ptRow(i); it < ptRow(i + 1); it++) {
const int icol = indCol(it);
// does not count diagonal
if (icol != i) {
for (int k = 0; k < n; k++) {
if (permute[k] == icol) {
width[k]++;
break;
}
}
} // if (icol != i)
}
} // loop : i
dist_ptRows[0] = 0;
for (int i = 0; i < n; i++) {
dist_ptRows[i + 1] = dist_ptRows[i] + width[i];
}
delete [] width;
dist = new SparseMatrix(n, dist_ptRows[n], dist_ptRows,
false, false, false);
if (isUpper()) {
for (int k = 0; k < n; k++) {
const int irow = permute[k];
int jt = dist->ptRow(k);
for (int i = 0; i < irow; i++) {
for (int it = ptRow(i); it < ptRow(i + 1); it++) {
const int icol = indCol(it);
// strictly lower == not touch the diagonal
if (icol != i) {
if (irow == icol) {
dist->indCol(jt) = i;
dist->Coef(jt) = Coef(it);
jt++;
break;
}
}
}
} // loop : i
// copy upper to upper
for (int it = ptRow(irow); it < ptRow(irow + 1); it++) {
dist->indCol(jt) = indCol(it);
dist->Coef(jt) = Coef(it);
jt++;
}
} // loop : k
} // order of filling nonzero elements is different from the upper
else { // case to keep increaing indcols[]
for (int k = 0; k < n; k++) {
const int irow = permute[k];
int jt = dist->ptRow(k);
// copy lower to lower
for (int it = ptRow(irow); it < ptRow(irow + 1); it++) {
dist->indCol(jt) = indCol(it);
dist->Coef(jt) = Coef(it);
jt++;
}
for (int i = irow; i < dimension(); i++) {
for (int it = ptRow(i); it < ptRow(i + 1); it++) {
const int icol = indCol(it);
// strictly lower == not touch the diagonal
if (icol != i) {
if (irow == icol) {
dist->indCol(jt) = i;
dist->Coef(jt) = Coef(it);
jt++;
break;
}
}
}
} // loop : i
} // loop : k
}
} // if (_isSymmetric)
else {
dist_ptRows[0] = 0;
// non-zero pattern is symmetric
for (int i = 0; i < n; i++) {
const int m = permute[i];
dist_ptRows[i + 1] = (dist_ptRows[i] +
(source_ptRows[m + 1] - source_ptRows[m]));
}
// isOwner = true, isSym = false
dist = new SparseMatrix(n, dist_ptRows[n], dist_ptRows,
false, false, false);
if (transposed) {
for (int k = 0; k < n; k++) {
const int irow = permute[k];
int jt = dist->ptRow(k);
for (int i = 0; i < dimension(); i++) {
for (int it = ptRow(i); it < ptRow(i + 1); it++){
const int icol = indCol(it);
if (irow == icol) {
dist->indCol(jt) = i;
dist->Coef(jt) = Coef(it);
jt++;
break;
}
}
} // loop : i
}
}
else {
for (int k = 0; k < n; k++) {
const int irow = permute[k];
int it = ptRow(irow);
int jt = dist->ptRow(k);
// copy lower to lower
for (; it < ptRow(irow + 1); it++, jt++) {;
dist->indCol(jt) = indCol(it);
dist->Coef(jt) = Coef(it);
}
}
}
} // if (_isSymmetric)
return dist;
}
template
SparseMatrix* SparseMatrix::
PartialCopyCSR(vector &permute, const int n,
bool transposed);
template
SparseMatrix* SparseMatrix::
PartialCopyCSR(vector &permute, const int n,
bool transposed);
template
SparseMatrix >* SparseMatrix >::
PartialCopyCSR(vector &permute, const int n,
bool transposed);
template
SparseMatrix >* SparseMatrix >::
PartialCopyCSR(vector &permute, const int n,
bool transposed);
template
SparseMatrix* SparseMatrix::
PartialCopyCSR(vector &permute, const int n,
bool transposed);
template
SparseMatrix >* SparseMatrix >::
PartialCopyCSR(vector &permute, const int n,
bool transposed);
//
int CSR_sym2unsym(int *ptRows, int *indCols, int *toSym,
const int *ptSymRows,
const int *indSymCols,
const int dim, const bool upper_flag)
{
int* nbIndPerRow = new int[dim];
memset(nbIndPerRow, 0, dim*sizeof(int));
for (int i = 0; i < dim; i++) {
nbIndPerRow[i] += ptSymRows[i + 1] - ptSymRows[i];
int ibegin = ptSymRows[i] + (upper_flag ? 1 : 0);
int iend = ptSymRows[i + 1] + (upper_flag ? 0 : (-1));
for (int k = ibegin; k < iend; k++) {
nbIndPerRow[indSymCols[k]]++;
}
}
// Build ptRows array :
// ...................
ptRows[0] = 0;
for (int i = 0; i < dim; i++) {
ptRows[i + 1] = ptRows[i] + nbIndPerRow[i];
}
// CHECK(ptRows[dim] == (2 * nz - dim),
// "error in sym2unsym() : Wrong number of non zeros elemnts in ptRows !");
// Allocate and fill indices columns :
memset(nbIndPerRow, 0, (dim * sizeof(int)));
// for upper case, nbIndPerRow[i] keeps entries added by transposed operation
// but for lower case counts all nonzero entries in progress
for (int i = 0; i < dim; i++) {
int itmp = ptRows[i] + nbIndPerRow[i];
for (int k = ptSymRows[i]; k < ptSymRows[i + 1]; k++) {
indCols[itmp] = indSymCols[k];
toSym[itmp] = k;
itmp++;
} // loop : k
if (!upper_flag) {
nbIndPerRow[i] = itmp - ptRows[i];
}
// memcpy(indCols + (ptRows[i] + nbIndPerRow[i]),
// indSymCols + ptSymRows[i],
// (ptSymRows[i + 1] - ptSymRows[i]) * sizeof(int));
int ibegin = ptSymRows[i] + (upper_flag ? 1 : 0);
int iend = ptSymRows[i + 1] + (upper_flag ? 0 : (-1));
for (int k = ibegin; k < iend; k++) {
const int j = indSymCols[k];
const int jtmp = ptRows[j] + nbIndPerRow[j];
indCols[jtmp] = i;
toSym[jtmp] = k;
nbIndPerRow[j]++;
} // loop : k
} // loop : i
// extract other toSym[]
delete [] nbIndPerRow;
return ptRows[dim];
}