// ------------------------------------------------------------------------ // // SPDX-License-Identifier: LGPL-2.1-or-later // Copyright (C) 1999 - 2024 by the deal.II authors // // This file is part of the deal.II library. // // Part of the source code is dual licensed under Apache-2.0 WITH // LLVM-exception OR LGPL-2.1-or-later. Detailed license information // governing the source code and code contributions can be found in // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. // // ------------------------------------------------------------------------ #ifndef dealii_precondition_block_templates_h #define dealii_precondition_block_templates_h #include #include #include #include #include #include #include DEAL_II_NAMESPACE_OPEN template PreconditionBlock::AdditionalData::AdditionalData( const size_type block_size, const double relaxation, const bool invert_diagonal, const bool same_diagonal) : relaxation(relaxation) , block_size(block_size) , invert_diagonal(invert_diagonal) , same_diagonal(same_diagonal) , inversion(PreconditionBlockBase::gauss_jordan) , threshold(0.) {} template PreconditionBlock::PreconditionBlock(bool store) : PreconditionBlockBase(store) , blocksize(0) , A(nullptr, typeid(*this).name()) , relaxation(1.0) {} template void PreconditionBlock::clear() { PreconditionBlockBase::clear(); blocksize = 0; A = nullptr; } template void PreconditionBlock::initialize( const MatrixType &M, const AdditionalData parameters) { const size_type bsize = parameters.block_size; clear(); Assert(M.m() == M.n(), ExcNotQuadratic()); A = &M; Assert(bsize > 0, ExcIndexRange(bsize, 1, M.m())); Assert(A->m() % bsize == 0, ExcWrongBlockSize(bsize, A->m())); blocksize = bsize; relaxation = parameters.relaxation; const unsigned int nblocks = A->m() / bsize; this->reinit(nblocks, blocksize, parameters.same_diagonal, parameters.inversion); if (parameters.invert_diagonal) { if (permutation.size() == M.m()) invert_permuted_diagblocks(); else invert_diagblocks(); } } template void PreconditionBlock::initialize( const MatrixType &M, const std::vector &new_permutation, const std::vector &new_inverse_permutation, const AdditionalData parameters) { set_permutation(new_permutation, new_inverse_permutation); initialize(M, parameters); } template void PreconditionBlock::invert_permuted_diagblocks() { Assert(A != nullptr, ExcNotInitialized()); Assert(blocksize != 0, ExcNotInitialized()); const MatrixType &M = *A; Assert(this->inverses_ready() == 0, ExcInverseMatricesAlreadyExist()); AssertDimension(permutation.size(), M.m()); AssertDimension(inverse_permutation.size(), M.m()); FullMatrix M_cell(blocksize); if (this->same_diagonal()) { for (size_type row_cell = 0; row_cell < blocksize; ++row_cell) { typename MatrixType::const_iterator entry = M.begin(row_cell); const typename MatrixType::const_iterator row_end = M.end(row_cell); while (entry != row_end) { if (entry->column() < blocksize) M_cell(row_cell, entry->column()) = entry->value(); ++entry; } } if (this->store_diagonals()) this->diagonal(0) = M_cell; switch (this->inversion) { case PreconditionBlockBase::gauss_jordan: this->inverse(0).invert(M_cell); break; case PreconditionBlockBase::householder: this->inverse_householder(0).initialize(M_cell); break; case PreconditionBlockBase::svd: this->inverse_svd(0) = M_cell; this->inverse_svd(0).compute_inverse_svd(0.); break; default: DEAL_II_NOT_IMPLEMENTED(); } } else { // cell_row, cell_column are the // numbering of the blocks (cells). // row_cell, column_cell are the local // numbering of the unknowns in the // blocks. // row, column are the global numbering // of the unknowns. M_cell = 0; for (unsigned int cell = 0; cell < this->size(); ++cell) { const size_type cell_start = cell * blocksize; for (size_type row_cell = 0; row_cell < blocksize; ++row_cell) { const size_type urow = row_cell + cell_start; const size_type row = permutation[urow]; typename MatrixType::const_iterator entry = M.begin(row); const typename MatrixType::const_iterator row_end = M.end(row); for (; entry != row_end; ++entry) { // if (entry->column()column()] < cell_start) continue; const size_type column_cell = inverse_permutation[entry->column()] - cell_start; if (column_cell >= blocksize) continue; M_cell(row_cell, column_cell) = entry->value(); } } if (this->store_diagonals()) this->diagonal(cell) = M_cell; switch (this->inversion) { case PreconditionBlockBase::gauss_jordan: this->inverse(cell).invert(M_cell); break; case PreconditionBlockBase::householder: this->inverse_householder(cell).initialize(M_cell); break; case PreconditionBlockBase::svd: this->inverse_svd(cell) = M_cell; this->inverse_svd(cell).compute_inverse_svd(0.); break; default: DEAL_II_NOT_IMPLEMENTED(); } } } this->inverses_computed(true); } template template void PreconditionBlock::forward_step( Vector &dst, const Vector &prev, const Vector &src, const bool transpose_diagonal) const { Assert(this->A != nullptr, ExcNotInitialized()); const MatrixType &M = *this->A; if (permutation.size() != 0) Assert( permutation.size() == M.m() || permutation.size() == this->size(), ExcMessage( "Permutation vector size must be equal to either the number of blocks or the dimension of the system")); const bool permuted = (permutation.size() == M.m()); const bool cell_permuted = (permutation.size() == this->size()); Vector b_cell(this->blocksize), x_cell(this->blocksize); // cell_row, cell_column are the // numbering of the blocks (cells). // row_cell, column_cell are the local // numbering of the unknowns in the // blocks. // row, column are the global numbering // of the unknowns. size_type row, row_cell; number2 b_cell_row; // The diagonal block if the // inverses were not precomputed FullMatrix M_cell(this->blocksize); // Loop over all blocks for (unsigned int rawcell = 0; rawcell < this->size(); ++rawcell) { const unsigned int cell = cell_permuted ? permutation[rawcell] : rawcell; const size_type block_start = cell * this->blocksize; const size_type permuted_block_start = permuted ? permutation[block_start] : block_start; for (row = permuted_block_start, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) { const typename MatrixType::const_iterator row_end = M.end(row); typename MatrixType::const_iterator entry = M.begin(row); b_cell_row = src(row); for (; entry != row_end; ++entry) { const size_type column = entry->column(); const size_type inverse_permuted_column = permuted ? inverse_permutation[column] : column; b_cell_row -= entry->value() * prev(column); // TODO:[GK] Find out if this is really once column and once // permuted if (!this->inverses_ready() && inverse_permuted_column >= block_start && inverse_permuted_column < block_start + this->blocksize) { const size_type column_cell = column - block_start; if (transpose_diagonal) M_cell(column_cell, row_cell) = entry->value(); else M_cell(row_cell, column_cell) = entry->value(); } } b_cell(row_cell) = b_cell_row; } if (this->inverses_ready()) { if (transpose_diagonal) this->inverse_Tvmult(cell, x_cell, b_cell); else this->inverse_vmult(cell, x_cell, b_cell); } else { Householder house(M_cell); house.least_squares(x_cell, b_cell); } // distribute x_cell to dst for (row = permuted_block_start, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) dst(row) = prev(row) + this->relaxation * x_cell(row_cell); } } template template void PreconditionBlock::backward_step( Vector &dst, const Vector &prev, const Vector &src, const bool transpose_diagonal) const { Assert(this->A != nullptr, ExcNotInitialized()); const MatrixType &M = *this->A; if (permutation.size() != 0) Assert( permutation.size() == M.m() || permutation.size() == this->size(), ExcMessage( "Permutation vector size must be equal to either the number of blocks or the dimension of the system")); const bool permuted = (permutation.size() == M.m()); const bool cell_permuted = (permutation.size() == this->size()); Vector b_cell(this->blocksize), x_cell(this->blocksize); // cell_row, cell_column are the // numbering of the blocks (cells). // row_cell, column_cell are the local // numbering of the unknowns in the // blocks. // row, column are the global numbering // of the unknowns. size_type row, row_cell; number2 b_cell_row; FullMatrix M_cell(this->blocksize); for (unsigned int rawcell = this->size(); rawcell != 0;) { --rawcell; const unsigned int cell = cell_permuted ? permutation[rawcell] : rawcell; const size_type block_start = cell * this->blocksize; const size_type block_end = block_start + this->blocksize; const size_type permuted_block_start = permuted ? permutation[block_start] : block_start; for (row = permuted_block_start, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) { const typename MatrixType::const_iterator row_end = M.end(row); typename MatrixType::const_iterator entry = M.begin(row); b_cell_row = src(row); for (; entry != row_end; ++entry) { const size_type column = entry->column(); const size_type inverse_permuted_column = permuted ? inverse_permutation[column] : column; b_cell_row -= entry->value() * prev(column); if (!this->inverses_ready() && inverse_permuted_column < block_end && column >= block_start) { const size_type column_cell = column - block_start; // We need the // transpose of the // diagonal block, // so we switch row // and column // indices if (transpose_diagonal) M_cell(column_cell, row_cell) = entry->value(); else M_cell(row_cell, column_cell) = entry->value(); } } b_cell(row_cell) = b_cell_row; } if (this->inverses_ready()) { if (transpose_diagonal) this->inverse_Tvmult(cell, x_cell, b_cell); else this->inverse_vmult(cell, x_cell, b_cell); } else { Householder house(M_cell); house.least_squares(x_cell, b_cell); } // distribute x_cell to dst for (row = permuted_block_start, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) dst(row) = prev(row) + this->relaxation * x_cell(row_cell); } } template typename PreconditionBlock::size_type PreconditionBlock::block_size() const { return blocksize; } template void PreconditionBlock::invert_diagblocks() { Assert(A != nullptr, ExcNotInitialized()); Assert(blocksize != 0, ExcNotInitialized()); const MatrixType &M = *A; Assert(this->inverses_ready() == 0, ExcInverseMatricesAlreadyExist()); FullMatrix M_cell(blocksize); if (this->same_diagonal()) { for (size_type row_cell = 0; row_cell < blocksize; ++row_cell) { typename MatrixType::const_iterator entry = M.begin(row_cell); const typename MatrixType::const_iterator row_end = M.end(row_cell); while (entry != row_end) { if (entry->column() < blocksize) M_cell(row_cell, entry->column()) = entry->value(); ++entry; } } if (this->store_diagonals()) this->diagonal(0) = M_cell; switch (this->inversion) { case PreconditionBlockBase::gauss_jordan: this->inverse(0).invert(M_cell); break; case PreconditionBlockBase::householder: this->inverse_householder(0).initialize(M_cell); break; case PreconditionBlockBase::svd: this->inverse_svd(0) = M_cell; this->inverse_svd(0).compute_inverse_svd(1.e-12); break; default: DEAL_II_NOT_IMPLEMENTED(); } } else { M_cell = 0; for (unsigned int cell = 0; cell < this->size(); ++cell) { const size_type cell_start = cell * blocksize; for (size_type row_cell = 0; row_cell < blocksize; ++row_cell) { const size_type row = row_cell + cell_start; typename MatrixType::const_iterator entry = M.begin(row); const typename MatrixType::const_iterator row_end = M.end(row); for (; entry != row_end; ++entry) { if (entry->column() < cell_start) continue; const size_type column_cell = entry->column() - cell_start; if (column_cell >= blocksize) continue; M_cell(row_cell, column_cell) = entry->value(); } } if (this->store_diagonals()) this->diagonal(cell) = M_cell; switch (this->inversion) { case PreconditionBlockBase::gauss_jordan: this->inverse(cell).invert(M_cell); break; case PreconditionBlockBase::householder: this->inverse_householder(cell).initialize(M_cell); break; case PreconditionBlockBase::svd: this->inverse_svd(cell) = M_cell; this->inverse_svd(cell).compute_inverse_svd(1.e-12); break; default: DEAL_II_NOT_IMPLEMENTED(); } } } this->inverses_computed(true); } template void PreconditionBlock::set_permutation( const std::vector &new_permutation, const std::vector &new_inverse_permutation) { AssertDimension(new_permutation.size(), new_inverse_permutation.size()); if (this->inverses_ready()) { AssertDimension(new_permutation.size(), this->size()); } permutation = new_permutation; inverse_permutation = new_inverse_permutation; } template std::size_t PreconditionBlock::memory_consumption() const { return (sizeof(*this) - sizeof(PreconditionBlockBase) + PreconditionBlockBase::memory_consumption()); } /*--------------------- PreconditionBlockJacobi -----------------------*/ template template void PreconditionBlockJacobi::do_vmult( Vector &dst, const Vector &src, bool adding) const { Assert(this->A != nullptr, ExcNotInitialized()); const MatrixType &M = *this->A; Vector b_cell(this->blocksize), x_cell(this->blocksize); // cell_row, cell_column are the // numbering of the blocks (cells). // row_cell, column_cell are the local // numbering of the unknowns in the // blocks. // row, column are the global numbering // of the unknowns. size_type row, row_cell, begin_diag_block = 0; if (!this->inverses_ready()) { FullMatrix M_cell(this->blocksize); for (unsigned int cell = 0; cell < this->size(); ++cell) { for (row = cell * this->blocksize, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) { b_cell(row_cell) = src(row); for (size_type column_cell = 0, column = cell * this->blocksize; column_cell < this->blocksize; ++column_cell, ++column) M_cell(row_cell, column_cell) = M(row, column); } Householder house(M_cell); house.least_squares(x_cell, b_cell); // distribute x_cell to dst for (row = cell * this->blocksize, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) if (adding) dst(row) += x_cell(row_cell); else dst(row) = x_cell(row_cell); begin_diag_block += this->blocksize; } } else for (unsigned int cell = 0; cell < this->size(); ++cell) { for (row = cell * this->blocksize, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) { b_cell(row_cell) = src(row); } this->inverse_vmult(cell, x_cell, b_cell); // distribute x_cell to dst for (row = cell * this->blocksize, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) if (adding) dst(row) += x_cell(row_cell); else dst(row) = x_cell(row_cell); begin_diag_block += this->blocksize; } dst *= this->relaxation; } template template void PreconditionBlockJacobi::vmult( Vector &dst, const Vector &src) const { do_vmult(dst, src, false); } template template void PreconditionBlockJacobi::Tvmult( Vector &dst, const Vector &src) const { do_vmult(dst, src, false); } template template void PreconditionBlockJacobi::vmult_add( Vector &dst, const Vector &src) const { do_vmult(dst, src, true); } template template void PreconditionBlockJacobi::Tvmult_add( Vector &dst, const Vector &src) const { do_vmult(dst, src, true); } template template void PreconditionBlockJacobi::step( Vector &dst, const Vector &src) const { GrowingVectorMemory> mem; typename VectorMemory>::Pointer aux(mem); aux->reinit(dst); this->forward_step(*aux, dst, src, false); dst = *aux; } template template void PreconditionBlockJacobi::Tstep( Vector &dst, const Vector &src) const { GrowingVectorMemory> mem; typename VectorMemory>::Pointer aux(mem); aux->reinit(dst); this->backward_step(*aux, dst, src, true); dst = *aux; } /*--------------------- PreconditionBlockSOR -----------------------*/ template PreconditionBlockSOR::PreconditionBlockSOR() : PreconditionBlock(false) {} template PreconditionBlockSOR::PreconditionBlockSOR(bool store) : PreconditionBlock(store) {} template template void PreconditionBlockSOR::forward( Vector &dst, const Vector &src, const bool transpose_diagonal, const bool) const { Assert(this->A != nullptr, ExcNotInitialized()); const MatrixType &M = *this->A; const bool permuted = (this->permutation.size() != 0); if (permuted) { Assert(this->permutation.size() == M.m(), ExcDimensionMismatch(this->permutation.size(), M.m())); } Vector b_cell(this->blocksize), x_cell(this->blocksize); // cell_row, cell_column are the // numbering of the blocks (cells). // row_cell, column_cell are the local // numbering of the unknowns in the // blocks. // row, column are the global numbering // of the unknowns. size_type row, row_cell, block_start = 0; number2 b_cell_row; // The diagonal block if the // inverses were not precomputed FullMatrix M_cell(this->blocksize); for (unsigned int cell = 0; cell < this->size(); ++cell) { const size_type permuted_block_start = permuted ? this->permutation[block_start] : block_start; for (row = permuted_block_start, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) { const typename MatrixType::const_iterator row_end = M.end(row); typename MatrixType::const_iterator entry = M.begin(row); b_cell_row = src(row); for (; entry != row_end; ++entry) { const size_type column = entry->column(); const size_type inverse_permuted_column = permuted ? this->inverse_permutation[column] : column; if (inverse_permuted_column < block_start) b_cell_row -= entry->value() * dst(column); else if (!this->inverses_ready() && column < block_start + this->blocksize) { const size_type column_cell = column - block_start; if (transpose_diagonal) M_cell(column_cell, row_cell) = entry->value(); else M_cell(row_cell, column_cell) = entry->value(); } } b_cell(row_cell) = b_cell_row; } if (this->inverses_ready()) { if (transpose_diagonal) this->inverse_Tvmult(cell, x_cell, b_cell); else this->inverse_vmult(cell, x_cell, b_cell); } else { Householder house(M_cell); house.least_squares(x_cell, b_cell); } // distribute x_cell to dst for (row = permuted_block_start, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) dst(row) = this->relaxation * x_cell(row_cell); block_start += this->blocksize; } } template template void PreconditionBlockSOR::backward( Vector &dst, const Vector &src, const bool transpose_diagonal, const bool) const { Assert(this->A != nullptr, ExcNotInitialized()); const MatrixType &M = *this->A; const bool permuted = (this->permutation.size() != 0); if (permuted) { Assert(this->permutation.size() == M.m(), ExcDimensionMismatch(this->permutation.size(), M.m())); } Vector b_cell(this->blocksize), x_cell(this->blocksize); // cell_row, cell_column are the // numbering of the blocks (cells). // row_cell, column_cell are the local // numbering of the unknowns in the // blocks. // row, column are the global numbering // of the unknowns. size_type row, row_cell; size_type block_end = this->blocksize * this->size(); number2 b_cell_row; FullMatrix M_cell(this->blocksize); for (unsigned int cell = this->size(); cell != 0;) { --cell; const size_type block_start = block_end - this->blocksize; // Collect upper triangle const size_type permuted_block_start = (this->permutation.size() != 0) ? this->permutation[block_start] : block_start; for (row = permuted_block_start, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) { const typename MatrixType::const_iterator row_end = M.end(row); typename MatrixType::const_iterator entry = M.begin(row); b_cell_row = src(row); for (; entry != row_end; ++entry) { const size_type column = entry->column(); const size_type inverse_permuted_column = permuted ? this->inverse_permutation[column] : column; if (inverse_permuted_column >= block_end) b_cell_row -= entry->value() * dst(column); else if (!this->inverses_ready() && column >= block_start) { const size_type column_cell = column - block_start; // We need the // transpose of the // diagonal block, // so we switch row // and column // indices if (transpose_diagonal) M_cell(column_cell, row_cell) = entry->value(); else M_cell(row_cell, column_cell) = entry->value(); } } b_cell(row_cell) = b_cell_row; } if (this->inverses_ready()) { if (transpose_diagonal) this->inverse_Tvmult(cell, x_cell, b_cell); else this->inverse_vmult(cell, x_cell, b_cell); } else { Householder house(M_cell); house.least_squares(x_cell, b_cell); } // distribute x_cell to dst for (row = permuted_block_start, row_cell = 0; row_cell < this->blocksize; ++row_cell, ++row) dst(row) = this->relaxation * x_cell(row_cell); block_end = block_start; } } template template void PreconditionBlockSOR::vmult( Vector &dst, const Vector &src) const { forward(dst, src, false, false); } template template void PreconditionBlockSOR::vmult_add( Vector &dst, const Vector &src) const { forward(dst, src, false, true); } template template void PreconditionBlockSOR::Tvmult( Vector &dst, const Vector &src) const { backward(dst, src, true, false); } template template void PreconditionBlockSOR::Tvmult_add( Vector &dst, const Vector &src) const { backward(dst, src, true, true); } template template void PreconditionBlockSOR::step( Vector &dst, const Vector &src) const { this->forward_step(dst, dst, src, false); } template template void PreconditionBlockSOR::Tstep( Vector &dst, const Vector &src) const { this->backward_step(dst, dst, src, true); } //--------------------------------------------------------------------------- template PreconditionBlockSSOR::PreconditionBlockSSOR() : PreconditionBlockSOR(true) {} template template void PreconditionBlockSSOR::vmult( Vector &dst, const Vector &src) const { Vector help; help.reinit(dst); this->forward(help, src, false, false); Vector cell_src(this->blocksize); Vector cell_dst(this->blocksize); const double scaling = (2. - this->relaxation) / this->relaxation; // Multiply with diagonal blocks for (unsigned int cell = 0; cell < this->size(); ++cell) { size_type row = cell * this->blocksize; for (size_type row_cell = 0; row_cell < this->blocksize; ++row_cell) cell_src(row_cell) = help(row + row_cell); this->diagonal(cell).vmult(cell_dst, cell_src); for (size_type row_cell = 0; row_cell < this->blocksize; ++row_cell) help(row + row_cell) = scaling * cell_dst(row_cell); } this->backward(dst, help, false, false); } template template void PreconditionBlockSSOR::Tvmult( Vector &dst, const Vector &src) const { Vector help; help.reinit(dst); this->backward(help, src, true, false); Vector cell_src(this->blocksize); Vector cell_dst(this->blocksize); const double scaling = (2. - this->relaxation) / this->relaxation; // Multiply with diagonal blocks for (unsigned int cell = 0; cell < this->size(); ++cell) { size_type row = cell * this->blocksize; for (size_type row_cell = 0; row_cell < this->blocksize; ++row_cell) cell_src(row_cell) = help(row + row_cell); this->diagonal(cell).Tvmult(cell_dst, cell_src); for (size_type row_cell = 0; row_cell < this->blocksize; ++row_cell) help(row + row_cell) = scaling * cell_dst(row_cell); } this->forward(dst, help, true, false); } template template void PreconditionBlockSSOR::step( Vector &dst, const Vector &src) const { this->forward_step(dst, dst, src, false); this->backward_step(dst, dst, src, false); } template template void PreconditionBlockSSOR::Tstep( Vector &dst, const Vector &src) const { this->backward_step(dst, dst, src, true); this->forward_step(dst, dst, src, true); } DEAL_II_NAMESPACE_CLOSE #endif