| 1 |
// ------------------------------------------------------------------------ |
| 2 |
// |
| 3 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 4 |
// Copyright (C) 1999 - 2025 by the deal.II authors |
| 5 |
// |
| 6 |
// This file is part of the deal.II library. |
| 7 |
// |
| 8 |
// Part of the source code is dual licensed under Apache-2.0 WITH |
| 9 |
// LLVM-exception OR LGPL-2.1-or-later. Detailed license information |
| 10 |
// governing the source code and code contributions can be found in |
| 11 |
// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. |
| 12 |
// |
| 13 |
// ------------------------------------------------------------------------ |
| 14 |
|
| 15 |
|
| 16 |
#ifndef dealii_sparse_matrix_templates_h |
| 17 |
#define dealii_sparse_matrix_templates_h |
| 18 |
|
| 19 |
#include <deal.II/base/config.h> |
| 20 |
|
| 21 |
#include <deal.II/base/parallel.h> |
| 22 |
#include <deal.II/base/template_constraints.h> |
| 23 |
#include <deal.II/base/utilities.h> |
| 24 |
|
| 25 |
#include <deal.II/lac/dynamic_sparsity_pattern.h> |
| 26 |
#include <deal.II/lac/full_matrix.h> |
| 27 |
#include <deal.II/lac/sparse_matrix.h> |
| 28 |
#include <deal.II/lac/trilinos_sparse_matrix.h> |
| 29 |
#include <deal.II/lac/vector.h> |
| 30 |
#include <deal.II/lac/vector_memory.h> |
| 31 |
|
| 32 |
#include <boost/io/ios_state.hpp> |
| 33 |
|
| 34 |
#include <algorithm> |
| 35 |
#include <cmath> |
| 36 |
#include <functional> |
| 37 |
#include <iomanip> |
| 38 |
#include <numeric> |
| 39 |
#include <ostream> |
| 40 |
#include <vector> |
| 41 |
|
| 42 |
|
| 43 |
|
| 44 |
DEAL_II_NAMESPACE_OPEN |
| 45 |
|
| 46 |
|
| 47 |
template <typename number> |
| 48 |
SparseMatrix<number>::SparseMatrix() |
| 49 |
: cols(nullptr, "SparseMatrix") |
| 50 |
, val(nullptr) |
| 51 |
, max_len(0) |
| 52 |
{} |
| 53 |
|
| 54 |
|
| 55 |
|
| 56 |
template <typename number> |
| 57 |
SparseMatrix<number>::SparseMatrix(const SparseMatrix &m) |
| 58 |
: EnableObserverPointer(m) |
| 59 |
, cols(nullptr, "SparseMatrix") |
| 60 |
, val(nullptr) |
| 61 |
, max_len(0) |
| 62 |
{ |
| 63 |
Assert(m.cols == nullptr && m.val == nullptr && m.max_len == 0, |
| 64 |
ExcMessage( |
| 65 |
"This constructor can only be called if the provided argument " |
| 66 |
"is an empty matrix. This constructor can not be used to " |
| 67 |
"copy-construct a non-empty matrix. Use the " |
| 68 |
"SparseMatrix::copy_from() function for that purpose.")); |
| 69 |
} |
| 70 |
|
| 71 |
|
| 72 |
|
| 73 |
template <typename number> |
| 74 |
SparseMatrix<number>::SparseMatrix(SparseMatrix<number> &&m) noexcept |
| 75 |
: EnableObserverPointer(std::move(m)) |
| 76 |
, cols(std::move(m.cols)) |
| 77 |
, val(std::move(m.val)) |
| 78 |
, max_len(m.max_len) |
| 79 |
{ |
| 80 |
m.cols = nullptr; |
| 81 |
m.val = nullptr; |
| 82 |
m.max_len = 0; |
| 83 |
} |
| 84 |
|
| 85 |
|
| 86 |
|
| 87 |
template <typename number> |
| 88 |
SparseMatrix<number> & |
| 89 |
SparseMatrix<number>::operator=(const SparseMatrix<number> &m) |
| 90 |
{ |
| 91 |
Assert(m.cols == nullptr && m.val == nullptr && m.max_len == 0, |
| 92 |
ExcMessage("This operator can only be called if the provided right " |
| 93 |
"hand side is an empty matrix. This operator can not be " |
| 94 |
"used to copy a non-empty matrix. Use the " |
| 95 |
"SparseMatrix::copy_from() function for that purpose.")); |
| 96 |
|
| 97 |
return *this; |
| 98 |
} |
| 99 |
|
| 100 |
|
| 101 |
|
| 102 |
template <typename number> |
| 103 |
SparseMatrix<number> & |
| 104 |
SparseMatrix<number>::operator=(SparseMatrix<number> &&m) noexcept |
| 105 |
{ |
| 106 |
cols = m.cols; |
| 107 |
val = std::move(m.val); |
| 108 |
max_len = m.max_len; |
| 109 |
|
| 110 |
m.cols = nullptr; |
| 111 |
m.val = nullptr; |
| 112 |
m.max_len = 0; |
| 113 |
|
| 114 |
return *this; |
| 115 |
} |
| 116 |
|
| 117 |
|
| 118 |
|
| 119 |
template <typename number> |
| 120 |
SparseMatrix<number>::SparseMatrix(const SparsityPattern &c) |
| 121 |
: cols(nullptr, "SparseMatrix") |
| 122 |
, val(nullptr) |
| 123 |
, max_len(0) |
| 124 |
{ |
| 125 |
// virtual functions called in constructors and destructors never use the |
| 126 |
// override in a derived class |
| 127 |
// for clarity be explicit on which function is called |
| 128 |
SparseMatrix<number>::reinit(c); |
| 129 |
} |
| 130 |
|
| 131 |
|
| 132 |
|
| 133 |
template <typename number> |
| 134 |
SparseMatrix<number>::SparseMatrix(const SparsityPattern &c, |
| 135 |
const IdentityMatrix &id) |
| 136 |
: cols(nullptr, "SparseMatrix") |
| 137 |
, val(nullptr) |
| 138 |
, max_len(0) |
| 139 |
{ |
| 140 |
Assert(c.n_rows() == id.m(), ExcDimensionMismatch(c.n_rows(), id.m())); |
| 141 |
Assert(c.n_cols() == id.n(), ExcDimensionMismatch(c.n_cols(), id.n())); |
| 142 |
|
| 143 |
// virtual functions called in constructors and destructors never use the |
| 144 |
// override in a derived class |
| 145 |
// for clarity be explicit on which function is called |
| 146 |
SparseMatrix<number>::reinit(c); |
| 147 |
for (size_type i = 0; i < n(); ++i) |
| 148 |
this->set(i, i, 1.); |
| 149 |
} |
| 150 |
|
| 151 |
|
| 152 |
|
| 153 |
template <typename number> |
| 154 |
SparseMatrix<number>::~SparseMatrix() |
| 155 |
{ |
| 156 |
cols = nullptr; |
| 157 |
} |
| 158 |
|
| 159 |
|
| 160 |
|
| 161 |
template <typename number> |
| 162 |
SparseMatrix<number> & |
| 163 |
SparseMatrix<number>::operator=(const double d) |
| 164 |
{ |
| 165 |
Assert(d == 0, ExcScalarAssignmentOnlyForZeroValue()); |
| 166 |
|
| 167 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 168 |
Assert(cols->compressed || cols->empty(), |
| 169 |
SparsityPattern::ExcNotCompressed()); |
| 170 |
|
| 171 |
// do initial zeroing of elements in parallel. Try to achieve a similar |
| 172 |
// layout as when doing matrix-vector products, as on some NUMA systems, a |
| 173 |
// memory block is assigned to memory banks where the first access is |
| 174 |
// generated. For sparse matrices, the first operations is usually the |
| 175 |
// operator=. The grain size is chosen to reflect the number of rows in |
| 176 |
// minimum_parallel_grain_size, weighted by the number of nonzero entries |
| 177 |
// per row on average. |
| 178 |
const std::size_t matrix_size = cols->n_nonzero_elements(); |
| 179 |
const size_type grain_size = |
| 180 |
internal::SparseMatrixImplementation::minimum_parallel_grain_size * |
| 181 |
(cols->n_nonzero_elements() + m()) / m(); |
| 182 |
if (matrix_size > grain_size) |
| 183 |
parallel::apply_to_subranges( |
| 184 |
0U, |
| 185 |
matrix_size, |
| 186 |
[values = this->val.get()](const size_type begin, const size_type end) { |
| 187 |
std::fill(values + begin, values + end, number(0.)); |
| 188 |
}, |
| 189 |
grain_size); |
| 190 |
else if (matrix_size > 0) |
| 191 |
{ |
| 192 |
std::fill(val.get(), val.get() + matrix_size, 0); |
| 193 |
} |
| 194 |
|
| 195 |
return *this; |
| 196 |
} |
| 197 |
|
| 198 |
|
| 199 |
|
| 200 |
template <typename number> |
| 201 |
SparseMatrix<number> & |
| 202 |
SparseMatrix<number>::operator=(const IdentityMatrix &id) |
| 203 |
{ |
| 204 |
Assert(cols->n_rows() == id.m(), |
| 205 |
ExcDimensionMismatch(cols->n_rows(), id.m())); |
| 206 |
Assert(cols->n_cols() == id.n(), |
| 207 |
ExcDimensionMismatch(cols->n_cols(), id.n())); |
| 208 |
|
| 209 |
*this = 0; |
| 210 |
for (size_type i = 0; i < n(); ++i) |
| 211 |
this->set(i, i, 1.); |
| 212 |
|
| 213 |
return *this; |
| 214 |
} |
| 215 |
|
| 216 |
|
| 217 |
|
| 218 |
template <typename number> |
| 219 |
void |
| 220 |
SparseMatrix<number>::reinit(const SparsityPattern &sparsity) |
| 221 |
{ |
| 222 |
cols = &sparsity; |
| 223 |
|
| 224 |
if (cols->empty()) |
| 225 |
{ |
| 226 |
val.reset(); |
| 227 |
max_len = 0; |
| 228 |
return; |
| 229 |
} |
| 230 |
|
| 231 |
const std::size_t N = cols->n_nonzero_elements(); |
| 232 |
if (N > max_len || max_len == 0) |
| 233 |
{ |
| 234 |
val = std::make_unique<number[]>(N); |
| 235 |
max_len = N; |
| 236 |
} |
| 237 |
|
| 238 |
*this = 0.; |
| 239 |
} |
| 240 |
|
| 241 |
|
| 242 |
|
| 243 |
template <typename number> |
| 244 |
void |
| 245 |
SparseMatrix<number>::clear() |
| 246 |
{ |
| 247 |
cols = nullptr; |
| 248 |
val.reset(); |
| 249 |
max_len = 0; |
| 250 |
} |
| 251 |
|
| 252 |
|
| 253 |
|
| 254 |
template <typename number> |
| 255 |
bool |
| 256 |
SparseMatrix<number>::empty() const |
| 257 |
{ |
| 258 |
if (cols == nullptr) |
| 259 |
return true; |
| 260 |
else |
| 261 |
return cols->empty(); |
| 262 |
} |
| 263 |
|
| 264 |
|
| 265 |
|
| 266 |
template <typename number> |
| 267 |
typename SparseMatrix<number>::size_type |
| 268 |
SparseMatrix<number>::get_row_length(const size_type row) const |
| 269 |
{ |
| 270 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 271 |
return cols->row_length(row); |
| 272 |
} |
| 273 |
|
| 274 |
|
| 275 |
|
| 276 |
template <typename number> |
| 277 |
std::size_t |
| 278 |
SparseMatrix<number>::n_nonzero_elements() const |
| 279 |
{ |
| 280 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 281 |
return cols->n_nonzero_elements(); |
| 282 |
} |
| 283 |
|
| 284 |
|
| 285 |
|
| 286 |
template <typename number> |
| 287 |
std::size_t |
| 288 |
SparseMatrix<number>::n_actually_nonzero_elements(const double threshold) const |
| 289 |
{ |
| 290 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 291 |
Assert(threshold >= 0, ExcMessage("Negative threshold!")); |
| 292 |
size_type nnz = 0; |
| 293 |
const std::size_t nnz_alloc = n_nonzero_elements(); |
| 294 |
for (size_type i = 0; i < nnz_alloc; ++i) |
| 295 |
if (std::abs(val[i]) > threshold) |
| 296 |
++nnz; |
| 297 |
return nnz; |
| 298 |
} |
| 299 |
|
| 300 |
|
| 301 |
|
| 302 |
template <typename number> |
| 303 |
void |
| 304 |
SparseMatrix<number>::symmetrize() |
| 305 |
{ |
| 306 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 307 |
Assert(cols->rows == cols->cols, ExcNotQuadratic()); |
| 308 |
|
| 309 |
const size_type n_rows = m(); |
| 310 |
for (size_type row = 0; row < n_rows; ++row) |
| 311 |
{ |
| 312 |
// first skip diagonal entry |
| 313 |
number *val_ptr = &val[cols->rowstart[row]]; |
| 314 |
if (m() == n()) |
| 315 |
++val_ptr; |
| 316 |
const size_type *colnum_ptr = &cols->colnums[cols->rowstart[row] + 1]; |
| 317 |
const number *const val_end_of_row = &val[cols->rowstart[row + 1]]; |
| 318 |
|
| 319 |
// treat lower left triangle |
| 320 |
while ((val_ptr != val_end_of_row) && (*colnum_ptr < row)) |
| 321 |
{ |
| 322 |
// compute the mean of this |
| 323 |
// and the transpose value |
| 324 |
const number mean_value = |
| 325 |
(*val_ptr + val[(*cols)(*colnum_ptr, row)]) / number(2.0); |
| 326 |
// set this value and the |
| 327 |
// transpose one to the |
| 328 |
// mean |
| 329 |
*val_ptr = mean_value; |
| 330 |
set(*colnum_ptr, row, mean_value); |
| 331 |
|
| 332 |
// advance pointers |
| 333 |
++val_ptr; |
| 334 |
++colnum_ptr; |
| 335 |
}; |
| 336 |
}; |
| 337 |
} |
| 338 |
|
| 339 |
|
| 340 |
|
| 341 |
template <typename number> |
| 342 |
template <typename somenumber> |
| 343 |
SparseMatrix<number> & |
| 344 |
SparseMatrix<number>::copy_from(const SparseMatrix<somenumber> &matrix) |
| 345 |
{ |
| 346 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 347 |
Assert(val != nullptr, ExcNotInitialized()); |
| 348 |
Assert(cols == matrix.cols, ExcDifferentSparsityPatterns()); |
| 349 |
|
| 350 |
std::copy(matrix.val.get(), |
| 351 |
matrix.val.get() + cols->n_nonzero_elements(), |
| 352 |
val.get()); |
| 353 |
|
| 354 |
return *this; |
| 355 |
} |
| 356 |
|
| 357 |
|
| 358 |
|
| 359 |
template <typename number> |
| 360 |
template <typename somenumber> |
| 361 |
void |
| 362 |
SparseMatrix<number>::copy_from(const FullMatrix<somenumber> &matrix) |
| 363 |
{ |
| 364 |
// first delete previous content |
| 365 |
*this = 0; |
| 366 |
|
| 367 |
// then copy old matrix |
| 368 |
for (size_type row = 0; row < matrix.m(); ++row) |
| 369 |
for (size_type col = 0; col < matrix.n(); ++col) |
| 370 |
if (matrix(row, col) != somenumber()) |
| 371 |
set(row, col, number(matrix(row, col))); |
| 372 |
} |
| 373 |
|
| 374 |
|
| 375 |
|
| 376 |
#ifdef DEAL_II_WITH_TRILINOS |
| 377 |
|
| 378 |
template <typename number> |
| 379 |
SparseMatrix<number> & |
| 380 |
SparseMatrix<number>::copy_from(const TrilinosWrappers::SparseMatrix &matrix) |
| 381 |
{ |
| 382 |
Assert(m() == matrix.m(), ExcDimensionMismatch(m(), matrix.m())); |
| 383 |
Assert(n() == matrix.n(), ExcDimensionMismatch(n(), matrix.n())); |
| 384 |
|
| 385 |
// first delete previous content |
| 386 |
*this = 0; |
| 387 |
|
| 388 |
std::vector<TrilinosScalar> value_cache; |
| 389 |
std::vector<size_type> colnum_cache; |
| 390 |
|
| 391 |
for (size_type row = 0; row < matrix.m(); ++row) |
| 392 |
{ |
| 393 |
value_cache.resize(matrix.n()); |
| 394 |
colnum_cache.resize(matrix.n()); |
| 395 |
|
| 396 |
// copy column indices and values and at the same time enquire about the |
| 397 |
// length of the row |
| 398 |
int ncols; |
| 399 |
int ierr = matrix.trilinos_matrix().ExtractGlobalRowCopy( |
| 400 |
row, |
| 401 |
matrix.row_length(row), |
| 402 |
ncols, |
| 403 |
value_cache.data(), |
| 404 |
reinterpret_cast<TrilinosWrappers::types::int_type *>( |
| 405 |
colnum_cache.data())); |
| 406 |
Assert(ierr == 0, ExcTrilinosError(ierr)); |
| 407 |
|
| 408 |
// resize arrays to the size actually used |
| 409 |
value_cache.resize(ncols); |
| 410 |
colnum_cache.resize(ncols); |
| 411 |
|
| 412 |
// then copy everything in one swoop |
| 413 |
this->set(row, colnum_cache, value_cache); |
| 414 |
} |
| 415 |
|
| 416 |
return *this; |
| 417 |
} |
| 418 |
|
| 419 |
#endif |
| 420 |
|
| 421 |
|
| 422 |
template <typename number> |
| 423 |
template <typename somenumber> |
| 424 |
void |
| 425 |
SparseMatrix<number>::add(const number factor, |
| 426 |
const SparseMatrix<somenumber> &matrix) |
| 427 |
{ |
| 428 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 429 |
Assert(val != nullptr, ExcNotInitialized()); |
| 430 |
Assert(cols == matrix.cols, ExcDifferentSparsityPatterns()); |
| 431 |
|
| 432 |
number *val_ptr = val.get(); |
| 433 |
const somenumber *matrix_ptr = matrix.val.get(); |
| 434 |
const number *const end_ptr = val.get() + cols->n_nonzero_elements(); |
| 435 |
|
| 436 |
while (val_ptr != end_ptr) |
| 437 |
*val_ptr++ += factor * number(*matrix_ptr++); |
| 438 |
} |
| 439 |
|
| 440 |
|
| 441 |
|
| 442 |
namespace internal |
| 443 |
{ |
| 444 |
namespace SparseMatrixImplementation |
| 445 |
{ |
| 446 |
using size_type = types::global_dof_index; |
| 447 |
|
| 448 |
/** |
| 449 |
* Perform a vmult using the SparseMatrix data structures, but only using |
| 450 |
* a subinterval for the row indices. |
| 451 |
* |
| 452 |
* In the sequential case, this function is called on all rows, in the |
| 453 |
* parallel case it may be called on a subrange, at the discretion of the |
| 454 |
* task scheduler. |
| 455 |
*/ |
| 456 |
template <typename number, typename InVector, typename OutVector> |
| 457 |
void |
| 458 |
vmult_on_subrange(const size_type begin_row, |
| 459 |
const size_type end_row, |
| 460 |
const number *values, |
| 461 |
const std::size_t *rowstart, |
| 462 |
const size_type *colnums, |
| 463 |
const InVector &src, |
| 464 |
OutVector &dst, |
| 465 |
const bool add) |
| 466 |
{ |
| 467 |
const number *val_ptr = &values[rowstart[begin_row]]; |
| 468 |
const size_type *colnum_ptr = &colnums[rowstart[begin_row]]; |
| 469 |
typename OutVector::iterator dst_ptr = dst.begin() + begin_row; |
| 470 |
|
| 471 |
if (add == false) |
| 472 |
for (size_type row = begin_row; row < end_row; ++row) |
| 473 |
{ |
| 474 |
typename OutVector::value_type s = 0.; |
| 475 |
const number *const val_end_of_row = &values[rowstart[row + 1]]; |
| 476 |
while (val_ptr != val_end_of_row) |
| 477 |
s += typename OutVector::value_type(*val_ptr++) * |
| 478 |
typename OutVector::value_type(src(*colnum_ptr++)); |
| 479 |
*dst_ptr++ = s; |
| 480 |
} |
| 481 |
else |
| 482 |
for (size_type row = begin_row; row < end_row; ++row) |
| 483 |
{ |
| 484 |
typename OutVector::value_type s = *dst_ptr; |
| 485 |
const number *const val_end_of_row = &values[rowstart[row + 1]]; |
| 486 |
while (val_ptr != val_end_of_row) |
| 487 |
s += typename OutVector::value_type(*val_ptr++) * |
| 488 |
typename OutVector::value_type(src(*colnum_ptr++)); |
| 489 |
*dst_ptr++ = s; |
| 490 |
} |
| 491 |
} |
| 492 |
} // namespace SparseMatrixImplementation |
| 493 |
} // namespace internal |
| 494 |
|
| 495 |
|
| 496 |
template <typename number> |
| 497 |
template <typename number2> |
| 498 |
void |
| 499 |
SparseMatrix<number>::add(const size_type row, |
| 500 |
const size_type n_cols, |
| 501 |
const size_type *col_indices, |
| 502 |
const number2 *values, |
| 503 |
const bool elide_zero_values, |
| 504 |
const bool col_indices_are_sorted) |
| 505 |
{ |
| 506 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 507 |
AssertIndexRange(row, m()); |
| 508 |
|
| 509 |
// if we have sufficiently many columns |
| 510 |
// and sorted indices it is faster to |
| 511 |
// just go through the column indices and |
| 512 |
// look whether we found one, rather than |
| 513 |
// doing many binary searches |
| 514 |
if (elide_zero_values == false && col_indices_are_sorted == true && |
| 515 |
n_cols > 3) |
| 516 |
{ |
| 517 |
// check whether the given indices are |
| 518 |
// really sorted |
| 519 |
if constexpr (running_in_debug_mode()) |
| 520 |
{ |
| 521 |
for (size_type i = 1; i < n_cols; ++i) |
| 522 |
Assert(col_indices[i] > col_indices[i - 1], |
| 523 |
ExcMessage( |
| 524 |
"List of indices is unsorted or contains duplicates.")); |
| 525 |
} |
| 526 |
|
| 527 |
const size_type *this_cols = &cols->colnums[cols->rowstart[row]]; |
| 528 |
const size_type row_length_1 = cols->row_length(row) - 1; |
| 529 |
number *val_ptr = &val[cols->rowstart[row]]; |
| 530 |
|
| 531 |
if (m() == n()) |
| 532 |
{ |
| 533 |
// find diagonal and add it if found |
| 534 |
Assert(this_cols[0] == row, ExcInternalError()); |
| 535 |
const size_type *diag_pos = |
| 536 |
Utilities::lower_bound(col_indices, col_indices + n_cols, row); |
| 537 |
const size_type diag = diag_pos - col_indices; |
| 538 |
size_type post_diag = diag; |
| 539 |
if (diag != n_cols && *diag_pos == row) |
| 540 |
{ |
| 541 |
val_ptr[0] += *(values + (diag_pos - col_indices)); |
| 542 |
++post_diag; |
| 543 |
} |
| 544 |
|
| 545 |
// Add indices before diagonal. Because the input array |
| 546 |
// is sorted, and because the entries in this matrix row |
| 547 |
// are sorted, we can just linearly walk the colnums array |
| 548 |
// and the input array in parallel, stopping whenever the |
| 549 |
// former matches the column index of the next index in |
| 550 |
// the input array: |
| 551 |
size_type counter = 1; |
| 552 |
for (size_type i = 0; i < diag; ++i) |
| 553 |
{ |
| 554 |
while (this_cols[counter] < col_indices[i] && |
| 555 |
counter < row_length_1) |
| 556 |
++counter; |
| 557 |
|
| 558 |
Assert((this_cols[counter] == col_indices[i]) || |
| 559 |
(values[i] == number2()), |
| 560 |
ExcInvalidIndex(row, col_indices[i])); |
| 561 |
|
| 562 |
val_ptr[counter] += values[i]; |
| 563 |
} |
| 564 |
|
| 565 |
// Then do the same to add indices after the diagonal: |
| 566 |
for (size_type i = post_diag; i < n_cols; ++i) |
| 567 |
{ |
| 568 |
while (this_cols[counter] < col_indices[i] && |
| 569 |
counter < row_length_1) |
| 570 |
++counter; |
| 571 |
|
| 572 |
Assert((this_cols[counter] == col_indices[i]) || |
| 573 |
(values[i] == number2()), |
| 574 |
ExcInvalidIndex(row, col_indices[i])); |
| 575 |
|
| 576 |
val_ptr[counter] += values[i]; |
| 577 |
} |
| 578 |
|
| 579 |
Assert(counter < cols->row_length(row), |
| 580 |
ExcMessage( |
| 581 |
"Specified invalid column indices in add function.")); |
| 582 |
} |
| 583 |
else |
| 584 |
{ |
| 585 |
// Use the same algorithm as above, but because the matrix is |
| 586 |
// not square, we can now do without the split for diagonal/ |
| 587 |
// entries before the diagonal/entries are the diagonal. |
| 588 |
size_type counter = 0; |
| 589 |
for (size_type i = 0; i < n_cols; ++i) |
| 590 |
{ |
| 591 |
while (this_cols[counter] < col_indices[i] && |
| 592 |
counter < row_length_1) |
| 593 |
++counter; |
| 594 |
|
| 595 |
Assert((this_cols[counter] == col_indices[i]) || |
| 596 |
(values[i] == number2()), |
| 597 |
ExcInvalidIndex(row, col_indices[i])); |
| 598 |
|
| 599 |
val_ptr[counter] += values[i]; |
| 600 |
} |
| 601 |
Assert(counter < cols->row_length(row), |
| 602 |
ExcMessage( |
| 603 |
"Specified invalid column indices in add function.")); |
| 604 |
} |
| 605 |
return; |
| 606 |
} |
| 607 |
|
| 608 |
// unsorted case: first, search all the |
| 609 |
// indices to find out which values we |
| 610 |
// actually need to add. |
| 611 |
const size_type *const my_cols = cols->colnums.get(); |
| 612 |
size_type index = cols->rowstart[row]; |
| 613 |
const size_type next_row_index = cols->rowstart[row + 1]; |
| 614 |
|
| 615 |
for (size_type j = 0; j < n_cols; ++j) |
| 616 |
{ |
| 617 |
const number value = number(values[j]); |
| 618 |
AssertIsFinite(value); |
| 619 |
|
| 620 |
if constexpr (running_in_debug_mode()) |
| 621 |
{ |
| 622 |
if (elide_zero_values == true && value == number()) |
| 623 |
continue; |
| 624 |
} |
| 625 |
else |
| 626 |
{ |
| 627 |
if (value == number()) |
| 628 |
continue; |
| 629 |
} |
| 630 |
|
| 631 |
// check whether the next index to add is |
| 632 |
// the next present index in the sparsity |
| 633 |
// pattern (otherwise, do a binary |
| 634 |
// search) |
| 635 |
if (index < next_row_index && my_cols[index] == col_indices[j]) |
| 636 |
goto add_value; |
| 637 |
|
| 638 |
index = cols->operator()(row, col_indices[j]); |
| 639 |
|
| 640 |
// it is allowed to add elements to |
| 641 |
// the matrix that are not part of |
| 642 |
// the sparsity pattern, if the |
| 643 |
// value we add is zero |
| 644 |
if (index == SparsityPattern::invalid_entry) |
| 645 |
{ |
| 646 |
Assert(value == number(), ExcInvalidIndex(row, col_indices[j])); |
| 647 |
continue; |
| 648 |
} |
| 649 |
|
| 650 |
add_value: |
| 651 |
val[index] += value; |
| 652 |
++index; |
| 653 |
} |
| 654 |
} |
| 655 |
|
| 656 |
|
| 657 |
|
| 658 |
template <typename number> |
| 659 |
template <typename number2> |
| 660 |
void |
| 661 |
SparseMatrix<number>::set(const size_type row, |
| 662 |
const size_type n_cols, |
| 663 |
const size_type *col_indices, |
| 664 |
const number2 *values, |
| 665 |
const bool elide_zero_values) |
| 666 |
{ |
| 667 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 668 |
AssertIndexRange(row, m()); |
| 669 |
|
| 670 |
// First, search all the indices to find |
| 671 |
// out which values we actually need to |
| 672 |
// set. |
| 673 |
const size_type *my_cols = cols->colnums.get(); |
| 674 |
std::size_t index = cols->rowstart[row], next_index = index; |
| 675 |
const std::size_t next_row_index = cols->rowstart[row + 1]; |
| 676 |
|
| 677 |
if (elide_zero_values == true) |
| 678 |
{ |
| 679 |
for (size_type j = 0; j < n_cols; ++j) |
| 680 |
{ |
| 681 |
const number value = number(values[j]); |
| 682 |
AssertIsFinite(value); |
| 683 |
|
| 684 |
if (value == number()) |
| 685 |
continue; |
| 686 |
|
| 687 |
// check whether the next index to set is |
| 688 |
// the next present index in the sparsity |
| 689 |
// pattern (otherwise, do a binary |
| 690 |
// search) |
| 691 |
if (index != next_row_index && my_cols[index] == col_indices[j]) |
| 692 |
goto set_value; |
| 693 |
|
| 694 |
next_index = cols->operator()(row, col_indices[j]); |
| 695 |
|
| 696 |
// it is allowed to set elements in |
| 697 |
// the matrix that are not part of |
| 698 |
// the sparsity pattern, if the |
| 699 |
// value to which we set it is zero |
| 700 |
if (next_index == SparsityPattern::invalid_entry) |
| 701 |
{ |
| 702 |
Assert(false, ExcInvalidIndex(row, col_indices[j])); |
| 703 |
continue; |
| 704 |
} |
| 705 |
index = next_index; |
| 706 |
|
| 707 |
set_value: |
| 708 |
val[index] = value; |
| 709 |
++index; |
| 710 |
} |
| 711 |
} |
| 712 |
else |
| 713 |
{ |
| 714 |
// same code as above, but now check for zeros |
| 715 |
for (size_type j = 0; j < n_cols; ++j) |
| 716 |
{ |
| 717 |
const number value = number(values[j]); |
| 718 |
AssertIsFinite(value); |
| 719 |
|
| 720 |
if (index != next_row_index && my_cols[index] == col_indices[j]) |
| 721 |
goto set_value_checked; |
| 722 |
|
| 723 |
next_index = cols->operator()(row, col_indices[j]); |
| 724 |
|
| 725 |
if (next_index == SparsityPattern::invalid_entry) |
| 726 |
{ |
| 727 |
Assert(value == number(), ExcInvalidIndex(row, col_indices[j])); |
| 728 |
continue; |
| 729 |
} |
| 730 |
index = next_index; |
| 731 |
|
| 732 |
set_value_checked: |
| 733 |
val[index] = value; |
| 734 |
++index; |
| 735 |
} |
| 736 |
} |
| 737 |
} |
| 738 |
|
| 739 |
|
| 740 |
|
| 741 |
template <typename number> |
| 742 |
template <class OutVector, class InVector> |
| 743 |
void |
| 744 |
SparseMatrix<number>::vmult(OutVector &dst, const InVector &src) const |
| 745 |
{ |
| 746 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 747 |
Assert(val != nullptr, ExcNotInitialized()); |
| 748 |
Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size())); |
| 749 |
Assert(n() == src.size(), ExcDimensionMismatch(n(), src.size())); |
| 750 |
|
| 751 |
Assert(!PointerComparison::equal(&src, &dst), ExcSourceEqualsDestination()); |
| 752 |
|
| 753 |
parallel::apply_to_subranges( |
| 754 |
0U, |
| 755 |
m(), |
| 756 |
[this, &src, &dst](const size_type begin_row, const size_type end_row) { |
| 757 |
internal::SparseMatrixImplementation::vmult_on_subrange( |
| 758 |
begin_row, |
| 759 |
end_row, |
| 760 |
val.get(), |
| 761 |
cols->rowstart.get(), |
| 762 |
cols->colnums.get(), |
| 763 |
src, |
| 764 |
dst, |
| 765 |
false); |
| 766 |
}, |
| 767 |
internal::SparseMatrixImplementation::minimum_parallel_grain_size); |
| 768 |
} |
| 769 |
|
| 770 |
|
| 771 |
|
| 772 |
template <typename number> |
| 773 |
template <class OutVector, class InVector> |
| 774 |
void |
| 775 |
SparseMatrix<number>::Tvmult(OutVector &dst, const InVector &src) const |
| 776 |
{ |
| 777 |
Assert(val != nullptr, ExcNotInitialized()); |
| 778 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 779 |
Assert(n() == dst.size(), ExcDimensionMismatch(n(), dst.size())); |
| 780 |
Assert(m() == src.size(), ExcDimensionMismatch(m(), src.size())); |
| 781 |
|
| 782 |
Assert(!PointerComparison::equal(&src, &dst), ExcSourceEqualsDestination()); |
| 783 |
|
| 784 |
dst = 0; |
| 785 |
|
| 786 |
for (size_type i = 0; i < m(); ++i) |
| 787 |
{ |
| 788 |
for (size_type j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j) |
| 789 |
{ |
| 790 |
const size_type p = cols->colnums[j]; |
| 791 |
dst(p) += typename OutVector::value_type(val[j]) * |
| 792 |
typename OutVector::value_type(src(i)); |
| 793 |
} |
| 794 |
} |
| 795 |
} |
| 796 |
|
| 797 |
|
| 798 |
|
| 799 |
template <typename number> |
| 800 |
template <class OutVector, class InVector> |
| 801 |
void |
| 802 |
SparseMatrix<number>::vmult_add(OutVector &dst, const InVector &src) const |
| 803 |
{ |
| 804 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 805 |
Assert(val != nullptr, ExcNotInitialized()); |
| 806 |
Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size())); |
| 807 |
Assert(n() == src.size(), ExcDimensionMismatch(n(), src.size())); |
| 808 |
|
| 809 |
Assert(!PointerComparison::equal(&src, &dst), ExcSourceEqualsDestination()); |
| 810 |
|
| 811 |
parallel::apply_to_subranges( |
| 812 |
0U, |
| 813 |
m(), |
| 814 |
[this, &src, &dst](const size_type begin_row, const size_type end_row) { |
| 815 |
internal::SparseMatrixImplementation::vmult_on_subrange( |
| 816 |
begin_row, |
| 817 |
end_row, |
| 818 |
val.get(), |
| 819 |
cols->rowstart.get(), |
| 820 |
cols->colnums.get(), |
| 821 |
src, |
| 822 |
dst, |
| 823 |
true); |
| 824 |
}, |
| 825 |
internal::SparseMatrixImplementation::minimum_parallel_grain_size); |
| 826 |
} |
| 827 |
|
| 828 |
|
| 829 |
|
| 830 |
template <typename number> |
| 831 |
template <class OutVector, class InVector> |
| 832 |
void |
| 833 |
SparseMatrix<number>::Tvmult_add(OutVector &dst, const InVector &src) const |
| 834 |
{ |
| 835 |
Assert(val != nullptr, ExcNotInitialized()); |
| 836 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 837 |
Assert(n() == dst.size(), ExcDimensionMismatch(n(), dst.size())); |
| 838 |
Assert(m() == src.size(), ExcDimensionMismatch(m(), src.size())); |
| 839 |
|
| 840 |
Assert(!PointerComparison::equal(&src, &dst), ExcSourceEqualsDestination()); |
| 841 |
|
| 842 |
for (size_type i = 0; i < m(); ++i) |
| 843 |
for (size_type j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j) |
| 844 |
{ |
| 845 |
const size_type p = cols->colnums[j]; |
| 846 |
dst(p) += typename OutVector::value_type(val[j]) * |
| 847 |
typename OutVector::value_type(src(i)); |
| 848 |
} |
| 849 |
} |
| 850 |
|
| 851 |
|
| 852 |
namespace internal |
| 853 |
{ |
| 854 |
namespace SparseMatrixImplementation |
| 855 |
{ |
| 856 |
/** |
| 857 |
* Perform a vmult using the SparseMatrix data structures, but only using |
| 858 |
* a subinterval for the row indices. |
| 859 |
* |
| 860 |
* In the sequential case, this function is called on all rows, in the |
| 861 |
* parallel case it may be called on a subrange, at the discretion of the |
| 862 |
* task scheduler. |
| 863 |
*/ |
| 864 |
template <typename number, typename InVector> |
| 865 |
typename InVector::value_type |
| 866 |
matrix_norm_sqr_on_subrange(const size_type begin_row, |
| 867 |
const size_type end_row, |
| 868 |
const number *values, |
| 869 |
const std::size_t *rowstart, |
| 870 |
const size_type *colnums, |
| 871 |
const InVector &v) |
| 872 |
{ |
| 873 |
typename InVector::value_type norm_sqr = 0.; |
| 874 |
|
| 875 |
for (size_type i = begin_row; i < end_row; ++i) |
| 876 |
{ |
| 877 |
typename InVector::value_type s = 0; |
| 878 |
for (size_type j = rowstart[i]; j < rowstart[i + 1]; ++j) |
| 879 |
s += typename InVector::value_type(values[j]) * v(colnums[j]); |
| 880 |
norm_sqr += |
| 881 |
v(i) * |
| 882 |
numbers::NumberTraits<typename InVector::value_type>::conjugate(s); |
| 883 |
} |
| 884 |
return norm_sqr; |
| 885 |
} |
| 886 |
} // namespace SparseMatrixImplementation |
| 887 |
} // namespace internal |
| 888 |
|
| 889 |
|
| 890 |
|
| 891 |
template <typename number> |
| 892 |
template <typename somenumber> |
| 893 |
somenumber |
| 894 |
SparseMatrix<number>::matrix_norm_square(const Vector<somenumber> &v) const |
| 895 |
{ |
| 896 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 897 |
Assert(val != nullptr, ExcNotInitialized()); |
| 898 |
Assert(m() == v.size(), ExcDimensionMismatch(m(), v.size())); |
| 899 |
Assert(n() == v.size(), ExcDimensionMismatch(n(), v.size())); |
| 900 |
|
| 901 |
return parallel::accumulate_from_subranges<somenumber>( |
| 902 |
[this, &v](const size_type begin_row, const size_type end_row) { |
| 903 |
return internal::SparseMatrixImplementation::matrix_norm_sqr_on_subrange( |
| 904 |
begin_row, |
| 905 |
end_row, |
| 906 |
val.get(), |
| 907 |
cols->rowstart.get(), |
| 908 |
cols->colnums.get(), |
| 909 |
v); |
| 910 |
}, |
| 911 |
0, |
| 912 |
m(), |
| 913 |
internal::SparseMatrixImplementation::minimum_parallel_grain_size); |
| 914 |
} |
| 915 |
|
| 916 |
|
| 917 |
|
| 918 |
namespace internal |
| 919 |
{ |
| 920 |
namespace SparseMatrixImplementation |
| 921 |
{ |
| 922 |
/** |
| 923 |
* Perform a vmult using the SparseMatrix data structures, but only using |
| 924 |
* a subinterval for the row indices. |
| 925 |
* |
| 926 |
* In the sequential case, this function is called on all rows, in the |
| 927 |
* parallel case it may be called on a subrange, at the discretion of the |
| 928 |
* task scheduler. |
| 929 |
*/ |
| 930 |
template <typename number, typename InVector> |
| 931 |
typename InVector::value_type |
| 932 |
matrix_scalar_product_on_subrange(const size_type begin_row, |
| 933 |
const size_type end_row, |
| 934 |
const number *values, |
| 935 |
const std::size_t *rowstart, |
| 936 |
const size_type *colnums, |
| 937 |
const InVector &u, |
| 938 |
const InVector &v) |
| 939 |
{ |
| 940 |
typename InVector::value_type norm_sqr = 0.; |
| 941 |
|
| 942 |
for (size_type i = begin_row; i < end_row; ++i) |
| 943 |
{ |
| 944 |
typename InVector::value_type s = 0; |
| 945 |
for (size_type j = rowstart[i]; j < rowstart[i + 1]; ++j) |
| 946 |
s += typename InVector::value_type(values[j]) * v(colnums[j]); |
| 947 |
norm_sqr += |
| 948 |
u(i) * |
| 949 |
numbers::NumberTraits<typename InVector::value_type>::conjugate(s); |
| 950 |
} |
| 951 |
return norm_sqr; |
| 952 |
} |
| 953 |
} // namespace SparseMatrixImplementation |
| 954 |
} // namespace internal |
| 955 |
|
| 956 |
|
| 957 |
|
| 958 |
template <typename number> |
| 959 |
template <typename somenumber> |
| 960 |
somenumber |
| 961 |
SparseMatrix<number>::matrix_scalar_product(const Vector<somenumber> &u, |
| 962 |
const Vector<somenumber> &v) const |
| 963 |
{ |
| 964 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 965 |
Assert(val != nullptr, ExcNotInitialized()); |
| 966 |
Assert(m() == u.size(), ExcDimensionMismatch(m(), u.size())); |
| 967 |
Assert(n() == v.size(), ExcDimensionMismatch(n(), v.size())); |
| 968 |
|
| 969 |
return parallel::accumulate_from_subranges<somenumber>( |
| 970 |
[this, &u, &v](const size_type begin_row, const size_type end_row) { |
| 971 |
return internal::SparseMatrixImplementation:: |
| 972 |
matrix_scalar_product_on_subrange(begin_row, |
| 973 |
end_row, |
| 974 |
val.get(), |
| 975 |
cols->rowstart.get(), |
| 976 |
cols->colnums.get(), |
| 977 |
u, |
| 978 |
v); |
| 979 |
}, |
| 980 |
0, |
| 981 |
m(), |
| 982 |
internal::SparseMatrixImplementation::minimum_parallel_grain_size); |
| 983 |
} |
| 984 |
|
| 985 |
|
| 986 |
|
| 987 |
template <typename number> |
| 988 |
template <typename numberB, typename numberC> |
| 989 |
void |
| 990 |
SparseMatrix<number>::mmult(SparseMatrix<numberC> &C, |
| 991 |
const SparseMatrix<numberB> &B, |
| 992 |
const Vector<number> &V, |
| 993 |
const bool rebuild_sparsity_C) const |
| 994 |
{ |
| 995 |
const bool use_vector = V.size() == n() ? true : false; |
| 996 |
Assert(n() == B.m(), ExcDimensionMismatch(n(), B.m())); |
| 997 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 998 |
Assert(B.cols != nullptr, ExcNeedsSparsityPattern()); |
| 999 |
Assert(C.cols != nullptr, ExcNeedsSparsityPattern()); |
| 1000 |
|
| 1001 |
const SparsityPattern &sp_A = *cols; |
| 1002 |
const SparsityPattern &sp_B = *B.cols; |
| 1003 |
|
| 1004 |
// clear previous content of C |
| 1005 |
if (rebuild_sparsity_C == true) |
| 1006 |
{ |
| 1007 |
// we are about to change the sparsity pattern of C. this can not work |
| 1008 |
// if either A or B use the same sparsity pattern |
| 1009 |
Assert(&C.get_sparsity_pattern() != &this->get_sparsity_pattern(), |
| 1010 |
ExcMessage("Can't use the same sparsity pattern for " |
| 1011 |
"different matrices if it is to be rebuilt.")); |
| 1012 |
Assert(&C.get_sparsity_pattern() != &B.get_sparsity_pattern(), |
| 1013 |
ExcMessage("Can't use the same sparsity pattern for " |
| 1014 |
"different matrices if it is to be rebuilt.")); |
| 1015 |
|
| 1016 |
// need to change the sparsity pattern of C, so cast away const-ness. |
| 1017 |
SparsityPattern &sp_C = |
| 1018 |
*(const_cast<SparsityPattern *>(&C.get_sparsity_pattern())); |
| 1019 |
C.clear(); |
| 1020 |
sp_C.reinit(0, 0, 0); |
| 1021 |
|
| 1022 |
// create a sparsity pattern for the matrix C. |
| 1023 |
{ |
| 1024 |
DynamicSparsityPattern dsp; |
| 1025 |
dsp.compute_mmult_pattern(sp_A, sp_B); |
| 1026 |
sp_C.copy_from(dsp); |
| 1027 |
} |
| 1028 |
|
| 1029 |
// reinit matrix C from that information |
| 1030 |
C.reinit(sp_C); |
| 1031 |
} |
| 1032 |
|
| 1033 |
Assert(C.m() == m(), ExcDimensionMismatch(C.m(), m())); |
| 1034 |
Assert(C.n() == B.n(), ExcDimensionMismatch(C.n(), B.n())); |
| 1035 |
|
| 1036 |
// create an array that caches some |
| 1037 |
// elements that are going to be written |
| 1038 |
// into the new matrix. |
| 1039 |
unsigned int max_n_cols_B = 0; |
| 1040 |
for (size_type i = 0; i < B.m(); ++i) |
| 1041 |
max_n_cols_B = std::max(max_n_cols_B, sp_B.row_length(i)); |
| 1042 |
std::vector<numberC> new_entries(max_n_cols_B); |
| 1043 |
|
| 1044 |
// now compute the actual entries: a matrix-matrix product involves three |
| 1045 |
// nested loops. One over the rows of A, for each row we then loop over all |
| 1046 |
// the columns, and then we need to multiply each element with all the |
| 1047 |
// elements in that row in B. |
| 1048 |
for (size_type i = 0; i < C.m(); ++i) |
| 1049 |
{ |
| 1050 |
const size_type *rows = &sp_A.colnums[sp_A.rowstart[i]]; |
| 1051 |
const size_type *const end_rows = &sp_A.colnums[sp_A.rowstart[i + 1]]; |
| 1052 |
for (; rows != end_rows; ++rows) |
| 1053 |
{ |
| 1054 |
const number A_val = val[rows - &sp_A.colnums[sp_A.rowstart[0]]]; |
| 1055 |
const size_type col = *rows; |
| 1056 |
const size_type *new_cols = (&sp_B.colnums[sp_B.rowstart[col]]); |
| 1057 |
|
| 1058 |
// special treatment for diagonal |
| 1059 |
if (sp_B.n_rows() == sp_B.n_cols()) |
| 1060 |
{ |
| 1061 |
C.add(i, |
| 1062 |
*new_cols, |
| 1063 |
numberC(A_val) * |
| 1064 |
numberC( |
| 1065 |
B.val[new_cols - &sp_B.colnums[sp_B.rowstart[0]]]) * |
| 1066 |
numberC(use_vector ? V(col) : 1)); |
| 1067 |
++new_cols; |
| 1068 |
} |
| 1069 |
|
| 1070 |
// now the innermost loop that goes over all the elements in row |
| 1071 |
// 'col' of matrix B. Cache the elements, and then write them into C |
| 1072 |
// at once |
| 1073 |
numberC *new_ptr = new_entries.data(); |
| 1074 |
const numberB *B_val_ptr = |
| 1075 |
&B.val[new_cols - &sp_B.colnums[sp_B.rowstart[0]]]; |
| 1076 |
const numberB *const end_cols = &B.val[sp_B.rowstart[col + 1]]; |
| 1077 |
for (; B_val_ptr != end_cols; ++B_val_ptr) |
| 1078 |
*new_ptr++ = numberC(A_val) * numberC(*B_val_ptr) * |
| 1079 |
numberC(use_vector ? V(col) : 1); |
| 1080 |
|
| 1081 |
C.add(i, |
| 1082 |
new_ptr - new_entries.data(), |
| 1083 |
new_cols, |
| 1084 |
new_entries.data(), |
| 1085 |
false, |
| 1086 |
true); |
| 1087 |
} |
| 1088 |
} |
| 1089 |
} |
| 1090 |
|
| 1091 |
|
| 1092 |
|
| 1093 |
template <typename number> |
| 1094 |
template <typename numberB, typename numberC> |
| 1095 |
void |
| 1096 |
SparseMatrix<number>::Tmmult(SparseMatrix<numberC> &C, |
| 1097 |
const SparseMatrix<numberB> &B, |
| 1098 |
const Vector<number> &V, |
| 1099 |
const bool rebuild_sparsity_C) const |
| 1100 |
{ |
| 1101 |
const bool use_vector = V.size() == m() ? true : false; |
| 1102 |
Assert(m() == B.m(), ExcDimensionMismatch(m(), B.m())); |
| 1103 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1104 |
Assert(B.cols != nullptr, ExcNeedsSparsityPattern()); |
| 1105 |
Assert(C.cols != nullptr, ExcNeedsSparsityPattern()); |
| 1106 |
|
| 1107 |
const SparsityPattern &sp_A = *cols; |
| 1108 |
const SparsityPattern &sp_B = *B.cols; |
| 1109 |
|
| 1110 |
// clear previous content of C |
| 1111 |
if (rebuild_sparsity_C == true) |
| 1112 |
{ |
| 1113 |
// we are about to change the sparsity pattern of C. this can not work |
| 1114 |
// if either A or B use the same sparsity pattern |
| 1115 |
Assert(&C.get_sparsity_pattern() != &this->get_sparsity_pattern(), |
| 1116 |
ExcMessage("Can't use the same sparsity pattern for " |
| 1117 |
"different matrices if it is to be rebuilt.")); |
| 1118 |
Assert(&C.get_sparsity_pattern() != &B.get_sparsity_pattern(), |
| 1119 |
ExcMessage("Can't use the same sparsity pattern for " |
| 1120 |
"different matrices if it is to be rebuilt.")); |
| 1121 |
|
| 1122 |
// need to change the sparsity pattern of C, so cast away const-ness. |
| 1123 |
SparsityPattern &sp_C = |
| 1124 |
*(const_cast<SparsityPattern *>(&C.get_sparsity_pattern())); |
| 1125 |
C.clear(); |
| 1126 |
sp_C.reinit(0, 0, 0); |
| 1127 |
|
| 1128 |
// create a sparsity pattern for the matrix. |
| 1129 |
{ |
| 1130 |
DynamicSparsityPattern dsp; |
| 1131 |
dsp.compute_Tmmult_pattern(sp_A, sp_B); |
| 1132 |
sp_C.copy_from(dsp); |
| 1133 |
} |
| 1134 |
|
| 1135 |
// reinit matrix C from that information |
| 1136 |
C.reinit(sp_C); |
| 1137 |
} |
| 1138 |
|
| 1139 |
Assert(C.m() == n(), ExcDimensionMismatch(C.m(), n())); |
| 1140 |
Assert(C.n() == B.n(), ExcDimensionMismatch(C.n(), B.n())); |
| 1141 |
|
| 1142 |
// create an array that caches some |
| 1143 |
// elements that are going to be written |
| 1144 |
// into the new matrix. |
| 1145 |
unsigned int max_n_cols_B = 0; |
| 1146 |
for (size_type i = 0; i < B.m(); ++i) |
| 1147 |
max_n_cols_B = std::max(max_n_cols_B, sp_B.row_length(i)); |
| 1148 |
std::vector<numberC> new_entries(max_n_cols_B); |
| 1149 |
|
| 1150 |
// now compute the actual entries: a matrix-matrix product involves three |
| 1151 |
// nested loops. One over the rows of A, for each row we then loop over all |
| 1152 |
// the columns, and then we need to multiply each element with all the |
| 1153 |
// elements in that row in B. |
| 1154 |
for (size_type i = 0; i < m(); ++i) |
| 1155 |
{ |
| 1156 |
const size_type *rows = &sp_A.colnums[sp_A.rowstart[i]]; |
| 1157 |
const size_type *const end_rows = &sp_A.colnums[sp_A.rowstart[i + 1]]; |
| 1158 |
const size_type *new_cols = &sp_B.colnums[sp_B.rowstart[i]]; |
| 1159 |
if (sp_B.n_rows() == sp_B.n_cols()) |
| 1160 |
++new_cols; |
| 1161 |
|
| 1162 |
const numberB *const end_cols = &B.val[sp_B.rowstart[i + 1]]; |
| 1163 |
|
| 1164 |
for (; rows != end_rows; ++rows) |
| 1165 |
{ |
| 1166 |
const size_type row = *rows; |
| 1167 |
const number A_val = val[rows - &sp_A.colnums[sp_A.rowstart[0]]]; |
| 1168 |
|
| 1169 |
// special treatment for diagonal |
| 1170 |
if (sp_B.n_rows() == sp_B.n_cols()) |
| 1171 |
C.add(row, |
| 1172 |
i, |
| 1173 |
numberC(A_val) * |
| 1174 |
numberC( |
| 1175 |
B.val[new_cols - 1 - &sp_B.colnums[sp_B.rowstart[0]]]) * |
| 1176 |
numberC(use_vector ? V(i) : 1)); |
| 1177 |
|
| 1178 |
// now the innermost loop that goes over all the elements in row |
| 1179 |
// 'col' of matrix B. Cache the elements, and then write them into C |
| 1180 |
// at once |
| 1181 |
numberC *new_ptr = new_entries.data(); |
| 1182 |
const numberB *B_val_ptr = |
| 1183 |
&B.val[new_cols - &sp_B.colnums[sp_B.rowstart[0]]]; |
| 1184 |
for (; B_val_ptr != end_cols; ++B_val_ptr) |
| 1185 |
*new_ptr++ = numberC(A_val) * numberC(*B_val_ptr) * |
| 1186 |
numberC(use_vector ? V(i) : 1); |
| 1187 |
|
| 1188 |
C.add(row, |
| 1189 |
new_ptr - new_entries.data(), |
| 1190 |
new_cols, |
| 1191 |
new_entries.data(), |
| 1192 |
false, |
| 1193 |
true); |
| 1194 |
} |
| 1195 |
} |
| 1196 |
} |
| 1197 |
|
| 1198 |
|
| 1199 |
|
| 1200 |
template <typename number> |
| 1201 |
typename SparseMatrix<number>::real_type |
| 1202 |
SparseMatrix<number>::l1_norm() const |
| 1203 |
{ |
| 1204 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1205 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1206 |
|
| 1207 |
Vector<real_type> column_sums(n()); |
| 1208 |
const size_type n_rows = m(); |
| 1209 |
for (size_type row = 0; row < n_rows; ++row) |
| 1210 |
for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j) |
| 1211 |
column_sums(cols->colnums[j]) += |
| 1212 |
numbers::NumberTraits<number>::abs(val[j]); |
| 1213 |
|
| 1214 |
return column_sums.linfty_norm(); |
| 1215 |
} |
| 1216 |
|
| 1217 |
|
| 1218 |
|
| 1219 |
template <typename number> |
| 1220 |
typename SparseMatrix<number>::real_type |
| 1221 |
SparseMatrix<number>::linfty_norm() const |
| 1222 |
{ |
| 1223 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1224 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1225 |
|
| 1226 |
const number *val_ptr = &val[cols->rowstart[0]]; |
| 1227 |
|
| 1228 |
real_type max = 0; |
| 1229 |
const size_type n_rows = m(); |
| 1230 |
for (size_type row = 0; row < n_rows; ++row) |
| 1231 |
{ |
| 1232 |
real_type sum = 0; |
| 1233 |
const number *const val_end_of_row = &val[cols->rowstart[row + 1]]; |
| 1234 |
while (val_ptr != val_end_of_row) |
| 1235 |
sum += numbers::NumberTraits<number>::abs(*val_ptr++); |
| 1236 |
if (sum > max) |
| 1237 |
max = sum; |
| 1238 |
} |
| 1239 |
return max; |
| 1240 |
} |
| 1241 |
|
| 1242 |
|
| 1243 |
|
| 1244 |
template <typename number> |
| 1245 |
typename SparseMatrix<number>::real_type |
| 1246 |
SparseMatrix<number>::frobenius_norm() const |
| 1247 |
{ |
| 1248 |
// simply add up all entries in the |
| 1249 |
// sparsity pattern, without taking any |
| 1250 |
// reference to rows or columns |
| 1251 |
real_type norm_sqr = 0; |
| 1252 |
const size_type n_rows = m(); |
| 1253 |
for (const number *ptr = val.get(); ptr != val.get() + cols->rowstart[n_rows]; |
| 1254 |
++ptr) |
| 1255 |
norm_sqr += numbers::NumberTraits<number>::abs_square(*ptr); |
| 1256 |
|
| 1257 |
return std::sqrt(norm_sqr); |
| 1258 |
} |
| 1259 |
|
| 1260 |
|
| 1261 |
|
| 1262 |
namespace internal |
| 1263 |
{ |
| 1264 |
namespace SparseMatrixImplementation |
| 1265 |
{ |
| 1266 |
/** |
| 1267 |
* Perform a vmult using the SparseMatrix data structures, but only using |
| 1268 |
* a subinterval for the row indices. |
| 1269 |
* |
| 1270 |
* In the sequential case, this function is called on all rows, in the |
| 1271 |
* parallel case it may be called on a subrange, at the discretion of the |
| 1272 |
* task scheduler. |
| 1273 |
*/ |
| 1274 |
template <typename number, typename InVector, typename OutVector> |
| 1275 |
typename OutVector::value_type |
| 1276 |
residual_sqr_on_subrange(const size_type begin_row, |
| 1277 |
const size_type end_row, |
| 1278 |
const number *values, |
| 1279 |
const std::size_t *rowstart, |
| 1280 |
const size_type *colnums, |
| 1281 |
const InVector &u, |
| 1282 |
const InVector &b, |
| 1283 |
OutVector &dst) |
| 1284 |
{ |
| 1285 |
typename OutVector::value_type norm_sqr = 0.; |
| 1286 |
|
| 1287 |
for (size_type i = begin_row; i < end_row; ++i) |
| 1288 |
{ |
| 1289 |
typename OutVector::value_type s = b(i); |
| 1290 |
for (size_type j = rowstart[i]; j < rowstart[i + 1]; ++j) |
| 1291 |
s -= typename OutVector::value_type(values[j]) * u(colnums[j]); |
| 1292 |
dst(i) = s; |
| 1293 |
norm_sqr += |
| 1294 |
s * |
| 1295 |
numbers::NumberTraits<typename OutVector::value_type>::conjugate(s); |
| 1296 |
} |
| 1297 |
return norm_sqr; |
| 1298 |
} |
| 1299 |
} // namespace SparseMatrixImplementation |
| 1300 |
} // namespace internal |
| 1301 |
|
| 1302 |
|
| 1303 |
template <typename number> |
| 1304 |
template <typename somenumber> |
| 1305 |
somenumber |
| 1306 |
SparseMatrix<number>::residual(Vector<somenumber> &dst, |
| 1307 |
const Vector<somenumber> &u, |
| 1308 |
const Vector<somenumber> &b) const |
| 1309 |
{ |
| 1310 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1311 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1312 |
Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size())); |
| 1313 |
Assert(m() == b.size(), ExcDimensionMismatch(m(), b.size())); |
| 1314 |
Assert(n() == u.size(), ExcDimensionMismatch(n(), u.size())); |
| 1315 |
|
| 1316 |
Assert(&u != &dst, ExcSourceEqualsDestination()); |
| 1317 |
|
| 1318 |
return std::sqrt(parallel::accumulate_from_subranges<somenumber>( |
| 1319 |
[this, &u, &b, &dst](const size_type begin_row, const size_type end_row) { |
| 1320 |
return internal::SparseMatrixImplementation::residual_sqr_on_subrange( |
| 1321 |
begin_row, |
| 1322 |
end_row, |
| 1323 |
val.get(), |
| 1324 |
cols->rowstart.get(), |
| 1325 |
cols->colnums.get(), |
| 1326 |
u, |
| 1327 |
b, |
| 1328 |
dst); |
| 1329 |
}, |
| 1330 |
0, |
| 1331 |
m(), |
| 1332 |
internal::SparseMatrixImplementation::minimum_parallel_grain_size)); |
| 1333 |
} |
| 1334 |
|
| 1335 |
|
| 1336 |
namespace internal |
| 1337 |
{ |
| 1338 |
namespace SparseMatrixImplementation |
| 1339 |
{ |
| 1340 |
// assert that the matrix has no zeros on the diagonal. this is important |
| 1341 |
// for preconditioners such as Jacobi or SSOR |
| 1342 |
template <typename number> |
| 1343 |
void |
| 1344 |
AssertNoZerosOnDiagonal(const SparseMatrix<number> &matrix) |
| 1345 |
{ |
| 1346 |
if constexpr (running_in_debug_mode()) |
| 1347 |
{ |
| 1348 |
for (typename SparseMatrix<number>::size_type row = 0; |
| 1349 |
row < matrix.m(); |
| 1350 |
++row) |
| 1351 |
Assert(matrix.diag_element(row) != number(), |
| 1352 |
ExcMessage( |
| 1353 |
"There is a zero on the diagonal of this matrix " |
| 1354 |
"in row " + |
| 1355 |
std::to_string(row) + |
| 1356 |
". The preconditioner you selected cannot work if that " |
| 1357 |
"is the case because one of its steps requires " |
| 1358 |
"division by the diagonal elements of the matrix." |
| 1359 |
"\n\n" |
| 1360 |
"You should check whether you have correctly " |
| 1361 |
"assembled the matrix that you use for this " |
| 1362 |
"preconditioner. If it is correct that there are " |
| 1363 |
"zeros on the diagonal, then you will have to chose " |
| 1364 |
"a different preconditioner.")); |
| 1365 |
} |
| 1366 |
else |
| 1367 |
{ |
| 1368 |
(void)matrix; |
| 1369 |
} |
| 1370 |
} |
| 1371 |
} // namespace SparseMatrixImplementation |
| 1372 |
} // namespace internal |
| 1373 |
|
| 1374 |
|
| 1375 |
template <typename number> |
| 1376 |
template <typename somenumber> |
| 1377 |
void |
| 1378 |
SparseMatrix<number>::precondition_Jacobi(Vector<somenumber> &dst, |
| 1379 |
const Vector<somenumber> &src, |
| 1380 |
const number omega) const |
| 1381 |
{ |
| 1382 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1383 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1384 |
AssertDimension(m(), n()); |
| 1385 |
AssertDimension(dst.size(), n()); |
| 1386 |
AssertDimension(src.size(), n()); |
| 1387 |
|
| 1388 |
internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this); |
| 1389 |
|
| 1390 |
const size_type n = src.size(); |
| 1391 |
somenumber *dst_ptr = dst.begin(); |
| 1392 |
const somenumber *src_ptr = src.begin(); |
| 1393 |
const std::size_t *rowstart_ptr = cols->rowstart.get(); |
| 1394 |
|
| 1395 |
// optimize the following loop for |
| 1396 |
// the case that the relaxation |
| 1397 |
// factor is one. In that case, we |
| 1398 |
// can save one FP multiplication |
| 1399 |
// per row |
| 1400 |
// |
| 1401 |
// note that for square matrices, |
| 1402 |
// the diagonal entry is the first |
| 1403 |
// in each row, i.e. at index |
| 1404 |
// rowstart[i]. and we do have a |
| 1405 |
// square matrix by above assertion |
| 1406 |
if (omega != number(1.)) |
| 1407 |
for (size_type i = 0; i < n; ++i, ++dst_ptr, ++src_ptr, ++rowstart_ptr) |
| 1408 |
*dst_ptr = somenumber(omega) * *src_ptr / somenumber(val[*rowstart_ptr]); |
| 1409 |
else |
| 1410 |
for (size_type i = 0; i < n; ++i, ++dst_ptr, ++src_ptr, ++rowstart_ptr) |
| 1411 |
*dst_ptr = *src_ptr / somenumber(val[*rowstart_ptr]); |
| 1412 |
} |
| 1413 |
|
| 1414 |
|
| 1415 |
|
| 1416 |
template <typename number> |
| 1417 |
template <typename somenumber> |
| 1418 |
void |
| 1419 |
SparseMatrix<number>::precondition_SSOR( |
| 1420 |
Vector<somenumber> &dst, |
| 1421 |
const Vector<somenumber> &src, |
| 1422 |
const number omega, |
| 1423 |
const std::vector<std::size_t> &pos_right_of_diagonal) const |
| 1424 |
{ |
| 1425 |
// to understand how this function works |
| 1426 |
// you may want to take a look at the CVS |
| 1427 |
// archives to see the original version |
| 1428 |
// which is much clearer... |
| 1429 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1430 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1431 |
AssertDimension(m(), n()); |
| 1432 |
AssertDimension(dst.size(), n()); |
| 1433 |
AssertDimension(src.size(), n()); |
| 1434 |
|
| 1435 |
internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this); |
| 1436 |
|
| 1437 |
const size_type n = src.size(); |
| 1438 |
const std::size_t *rowstart_ptr = cols->rowstart.get(); |
| 1439 |
somenumber *dst_ptr = &dst(0); |
| 1440 |
|
| 1441 |
// case when we have stored the position |
| 1442 |
// just right of the diagonal (then we |
| 1443 |
// don't have to search for it). |
| 1444 |
if (pos_right_of_diagonal.size() != 0) |
| 1445 |
{ |
| 1446 |
Assert(pos_right_of_diagonal.size() == dst.size(), |
| 1447 |
ExcDimensionMismatch(pos_right_of_diagonal.size(), dst.size())); |
| 1448 |
|
| 1449 |
// forward sweep |
| 1450 |
for (size_type row = 0; row < n; ++row, ++dst_ptr, ++rowstart_ptr) |
| 1451 |
{ |
| 1452 |
*dst_ptr = src(row); |
| 1453 |
const std::size_t first_right_of_diagonal_index = |
| 1454 |
pos_right_of_diagonal[row]; |
| 1455 |
Assert(first_right_of_diagonal_index <= *(rowstart_ptr + 1), |
| 1456 |
ExcInternalError()); |
| 1457 |
number s = 0; |
| 1458 |
for (size_type j = (*rowstart_ptr) + 1; |
| 1459 |
j < first_right_of_diagonal_index; |
| 1460 |
++j) |
| 1461 |
s += val[j] * number(dst(cols->colnums[j])); |
| 1462 |
|
| 1463 |
// divide by diagonal element |
| 1464 |
*dst_ptr -= s * omega; |
| 1465 |
*dst_ptr /= val[*rowstart_ptr]; |
| 1466 |
} |
| 1467 |
|
| 1468 |
rowstart_ptr = cols->rowstart.get(); |
| 1469 |
dst_ptr = &dst(0); |
| 1470 |
for (; rowstart_ptr != &cols->rowstart[n]; ++rowstart_ptr, ++dst_ptr) |
| 1471 |
*dst_ptr *= somenumber(omega * (number(2.) - omega)) * |
| 1472 |
somenumber(val[*rowstart_ptr]); |
| 1473 |
|
| 1474 |
// backward sweep |
| 1475 |
rowstart_ptr = &cols->rowstart[n - 1]; |
| 1476 |
dst_ptr = &dst(n - 1); |
| 1477 |
for (int row = n - 1; row >= 0; --row, --rowstart_ptr, --dst_ptr) |
| 1478 |
{ |
| 1479 |
const size_type end_row = *(rowstart_ptr + 1); |
| 1480 |
const size_type first_right_of_diagonal_index = |
| 1481 |
pos_right_of_diagonal[row]; |
| 1482 |
number s = 0; |
| 1483 |
// go through the column from the end towards the diagonal in order |
| 1484 |
// to delay the use of the newly computed "dst" values on |
| 1485 |
// out-of-order-execution hardware |
| 1486 |
for (size_type j = end_row - 1; j >= first_right_of_diagonal_index; |
| 1487 |
--j) |
| 1488 |
s += val[j] * number(dst(cols->colnums[j])); |
| 1489 |
|
| 1490 |
*dst_ptr -= s * omega; |
| 1491 |
*dst_ptr /= val[*rowstart_ptr]; |
| 1492 |
}; |
| 1493 |
return; |
| 1494 |
} |
| 1495 |
|
| 1496 |
// case when we need to get the position |
| 1497 |
// of the first element right of the |
| 1498 |
// diagonal manually for each sweep. |
| 1499 |
// forward sweep |
| 1500 |
for (size_type row = 0; row < n; ++row, ++dst_ptr, ++rowstart_ptr) |
| 1501 |
{ |
| 1502 |
*dst_ptr = src(row); |
| 1503 |
// find the first element in this line |
| 1504 |
// which is on the right of the diagonal. |
| 1505 |
// we need to precondition with the |
| 1506 |
// elements on the left only. |
| 1507 |
// note: the first entry in each |
| 1508 |
// line denotes the diagonal element, |
| 1509 |
// which we need not check. |
| 1510 |
const size_type first_right_of_diagonal_index = |
| 1511 |
(Utilities::lower_bound(cols->colnums.get() + *rowstart_ptr + 1, |
| 1512 |
cols->colnums.get() + *(rowstart_ptr + 1), |
| 1513 |
row) - |
| 1514 |
cols->colnums.get()); |
| 1515 |
|
| 1516 |
number s = 0; |
| 1517 |
for (size_type j = (*rowstart_ptr) + 1; j < first_right_of_diagonal_index; |
| 1518 |
++j) |
| 1519 |
s += val[j] * number(dst(cols->colnums[j])); |
| 1520 |
|
| 1521 |
// divide by diagonal element |
| 1522 |
*dst_ptr -= s * omega; |
| 1523 |
Assert(val[*rowstart_ptr] != number(), ExcDivideByZero()); |
| 1524 |
*dst_ptr /= val[*rowstart_ptr]; |
| 1525 |
}; |
| 1526 |
|
| 1527 |
rowstart_ptr = cols->rowstart.get(); |
| 1528 |
dst_ptr = &dst(0); |
| 1529 |
for (size_type row = 0; row < n; ++row, ++rowstart_ptr, ++dst_ptr) |
| 1530 |
*dst_ptr *= |
| 1531 |
somenumber((number(2.) - omega)) * somenumber(val[*rowstart_ptr]); |
| 1532 |
|
| 1533 |
// backward sweep |
| 1534 |
rowstart_ptr = &cols->rowstart[n - 1]; |
| 1535 |
dst_ptr = &dst(n - 1); |
| 1536 |
for (int row = n - 1; row >= 0; --row, --rowstart_ptr, --dst_ptr) |
| 1537 |
{ |
| 1538 |
const size_type end_row = *(rowstart_ptr + 1); |
| 1539 |
const size_type first_right_of_diagonal_index = |
| 1540 |
(Utilities::lower_bound(&cols->colnums[*rowstart_ptr + 1], |
| 1541 |
&cols->colnums[end_row], |
| 1542 |
static_cast<size_type>(row)) - |
| 1543 |
cols->colnums.get()); |
| 1544 |
number s = 0; |
| 1545 |
for (size_type j = first_right_of_diagonal_index; j < end_row; ++j) |
| 1546 |
s += val[j] * number(dst(cols->colnums[j])); |
| 1547 |
*dst_ptr -= s * omega; |
| 1548 |
Assert(val[*rowstart_ptr] != number(), ExcDivideByZero()); |
| 1549 |
*dst_ptr /= val[*rowstart_ptr]; |
| 1550 |
}; |
| 1551 |
} |
| 1552 |
|
| 1553 |
|
| 1554 |
template <typename number> |
| 1555 |
template <typename somenumber> |
| 1556 |
void |
| 1557 |
SparseMatrix<number>::precondition_SOR(Vector<somenumber> &dst, |
| 1558 |
const Vector<somenumber> &src, |
| 1559 |
const number omega) const |
| 1560 |
{ |
| 1561 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1562 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1563 |
|
| 1564 |
dst = src; |
| 1565 |
SOR(dst, omega); |
| 1566 |
} |
| 1567 |
|
| 1568 |
|
| 1569 |
template <typename number> |
| 1570 |
template <typename somenumber> |
| 1571 |
void |
| 1572 |
SparseMatrix<number>::precondition_TSOR(Vector<somenumber> &dst, |
| 1573 |
const Vector<somenumber> &src, |
| 1574 |
const number omega) const |
| 1575 |
{ |
| 1576 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1577 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1578 |
|
| 1579 |
dst = src; |
| 1580 |
TSOR(dst, omega); |
| 1581 |
} |
| 1582 |
|
| 1583 |
|
| 1584 |
template <typename number> |
| 1585 |
template <typename somenumber> |
| 1586 |
void |
| 1587 |
SparseMatrix<number>::SOR(Vector<somenumber> &dst, const number omega) const |
| 1588 |
{ |
| 1589 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1590 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1591 |
AssertDimension(m(), n()); |
| 1592 |
AssertDimension(dst.size(), n()); |
| 1593 |
|
| 1594 |
internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this); |
| 1595 |
|
| 1596 |
for (size_type row = 0; row < m(); ++row) |
| 1597 |
{ |
| 1598 |
somenumber s = dst(row); |
| 1599 |
for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j) |
| 1600 |
{ |
| 1601 |
const size_type col = cols->colnums[j]; |
| 1602 |
if (col < row) |
| 1603 |
s -= somenumber(val[j]) * dst(col); |
| 1604 |
} |
| 1605 |
|
| 1606 |
dst(row) = s * somenumber(omega) / somenumber(val[cols->rowstart[row]]); |
| 1607 |
} |
| 1608 |
} |
| 1609 |
|
| 1610 |
|
| 1611 |
template <typename number> |
| 1612 |
template <typename somenumber> |
| 1613 |
void |
| 1614 |
SparseMatrix<number>::TSOR(Vector<somenumber> &dst, const number omega) const |
| 1615 |
{ |
| 1616 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1617 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1618 |
AssertDimension(m(), n()); |
| 1619 |
AssertDimension(dst.size(), n()); |
| 1620 |
|
| 1621 |
internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this); |
| 1622 |
|
| 1623 |
size_type row = m() - 1; |
| 1624 |
while (true) |
| 1625 |
{ |
| 1626 |
somenumber s = dst(row); |
| 1627 |
for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j) |
| 1628 |
if (cols->colnums[j] > row) |
| 1629 |
s -= somenumber(val[j]) * dst(cols->colnums[j]); |
| 1630 |
|
| 1631 |
dst(row) = s * somenumber(omega) / somenumber(val[cols->rowstart[row]]); |
| 1632 |
|
| 1633 |
if (row == 0) |
| 1634 |
break; |
| 1635 |
|
| 1636 |
--row; |
| 1637 |
} |
| 1638 |
} |
| 1639 |
|
| 1640 |
|
| 1641 |
template <typename number> |
| 1642 |
template <typename somenumber> |
| 1643 |
void |
| 1644 |
SparseMatrix<number>::PSOR(Vector<somenumber> &dst, |
| 1645 |
const std::vector<size_type> &permutation, |
| 1646 |
const std::vector<size_type> &inverse_permutation, |
| 1647 |
const number omega) const |
| 1648 |
{ |
| 1649 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1650 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1651 |
AssertDimension(m(), n()); |
| 1652 |
|
| 1653 |
Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size())); |
| 1654 |
Assert(m() == permutation.size(), |
| 1655 |
ExcDimensionMismatch(m(), permutation.size())); |
| 1656 |
Assert(m() == inverse_permutation.size(), |
| 1657 |
ExcDimensionMismatch(m(), inverse_permutation.size())); |
| 1658 |
|
| 1659 |
internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this); |
| 1660 |
|
| 1661 |
for (size_type urow = 0; urow < m(); ++urow) |
| 1662 |
{ |
| 1663 |
const size_type row = permutation[urow]; |
| 1664 |
somenumber s = dst(row); |
| 1665 |
|
| 1666 |
for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j) |
| 1667 |
{ |
| 1668 |
const size_type col = cols->colnums[j]; |
| 1669 |
if (inverse_permutation[col] < urow) |
| 1670 |
{ |
| 1671 |
s -= somenumber(val[j]) * dst(col); |
| 1672 |
} |
| 1673 |
} |
| 1674 |
|
| 1675 |
dst(row) = s * somenumber(omega) / somenumber(val[cols->rowstart[row]]); |
| 1676 |
} |
| 1677 |
} |
| 1678 |
|
| 1679 |
|
| 1680 |
template <typename number> |
| 1681 |
template <typename somenumber> |
| 1682 |
void |
| 1683 |
SparseMatrix<number>::TPSOR(Vector<somenumber> &dst, |
| 1684 |
const std::vector<size_type> &permutation, |
| 1685 |
const std::vector<size_type> &inverse_permutation, |
| 1686 |
const number omega) const |
| 1687 |
{ |
| 1688 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1689 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1690 |
AssertDimension(m(), n()); |
| 1691 |
|
| 1692 |
Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size())); |
| 1693 |
Assert(m() == permutation.size(), |
| 1694 |
ExcDimensionMismatch(m(), permutation.size())); |
| 1695 |
Assert(m() == inverse_permutation.size(), |
| 1696 |
ExcDimensionMismatch(m(), inverse_permutation.size())); |
| 1697 |
|
| 1698 |
internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this); |
| 1699 |
|
| 1700 |
for (size_type urow = m(); urow != 0;) |
| 1701 |
{ |
| 1702 |
--urow; |
| 1703 |
const size_type row = permutation[urow]; |
| 1704 |
somenumber s = dst(row); |
| 1705 |
for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j) |
| 1706 |
{ |
| 1707 |
const size_type col = cols->colnums[j]; |
| 1708 |
if (inverse_permutation[col] > urow) |
| 1709 |
s -= somenumber(val[j]) * dst(col); |
| 1710 |
} |
| 1711 |
|
| 1712 |
dst(row) = s * somenumber(omega) / somenumber(val[cols->rowstart[row]]); |
| 1713 |
} |
| 1714 |
} |
| 1715 |
|
| 1716 |
|
| 1717 |
|
| 1718 |
template <typename number> |
| 1719 |
template <typename somenumber> |
| 1720 |
void |
| 1721 |
SparseMatrix<number>::Jacobi_step(Vector<somenumber> &v, |
| 1722 |
const Vector<somenumber> &b, |
| 1723 |
const number omega) const |
| 1724 |
{ |
| 1725 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1726 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1727 |
AssertDimension(m(), n()); |
| 1728 |
|
| 1729 |
Assert(m() == v.size(), ExcDimensionMismatch(m(), v.size())); |
| 1730 |
Assert(m() == b.size(), ExcDimensionMismatch(m(), b.size())); |
| 1731 |
|
| 1732 |
GrowingVectorMemory<Vector<somenumber>> mem; |
| 1733 |
typename VectorMemory<Vector<somenumber>>::Pointer w(mem); |
| 1734 |
w->reinit(v); |
| 1735 |
|
| 1736 |
if (!v.all_zero()) |
| 1737 |
{ |
| 1738 |
vmult(*w, v); |
| 1739 |
*w -= b; |
| 1740 |
} |
| 1741 |
else |
| 1742 |
w->equ(-1., b); |
| 1743 |
precondition_Jacobi(*w, *w, omega); |
| 1744 |
v -= *w; |
| 1745 |
} |
| 1746 |
|
| 1747 |
|
| 1748 |
|
| 1749 |
template <typename number> |
| 1750 |
template <typename somenumber> |
| 1751 |
void |
| 1752 |
SparseMatrix<number>::SOR_step(Vector<somenumber> &v, |
| 1753 |
const Vector<somenumber> &b, |
| 1754 |
const number omega) const |
| 1755 |
{ |
| 1756 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1757 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1758 |
AssertDimension(m(), n()); |
| 1759 |
Assert(m() == v.size(), ExcDimensionMismatch(m(), v.size())); |
| 1760 |
Assert(m() == b.size(), ExcDimensionMismatch(m(), b.size())); |
| 1761 |
|
| 1762 |
internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this); |
| 1763 |
|
| 1764 |
for (size_type row = 0; row < m(); ++row) |
| 1765 |
{ |
| 1766 |
somenumber s = b(row); |
| 1767 |
for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j) |
| 1768 |
{ |
| 1769 |
s -= somenumber(val[j]) * v(cols->colnums[j]); |
| 1770 |
} |
| 1771 |
v(row) += s * somenumber(omega) / somenumber(val[cols->rowstart[row]]); |
| 1772 |
} |
| 1773 |
} |
| 1774 |
|
| 1775 |
|
| 1776 |
|
| 1777 |
template <typename number> |
| 1778 |
template <typename somenumber> |
| 1779 |
void |
| 1780 |
SparseMatrix<number>::TSOR_step(Vector<somenumber> &v, |
| 1781 |
const Vector<somenumber> &b, |
| 1782 |
const number omega) const |
| 1783 |
{ |
| 1784 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1785 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1786 |
AssertDimension(m(), n()); |
| 1787 |
Assert(m() == v.size(), ExcDimensionMismatch(m(), v.size())); |
| 1788 |
Assert(m() == b.size(), ExcDimensionMismatch(m(), b.size())); |
| 1789 |
|
| 1790 |
internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this); |
| 1791 |
|
| 1792 |
for (int row = m() - 1; row >= 0; --row) |
| 1793 |
{ |
| 1794 |
somenumber s = b(row); |
| 1795 |
for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j) |
| 1796 |
{ |
| 1797 |
s -= somenumber(val[j]) * v(cols->colnums[j]); |
| 1798 |
} |
| 1799 |
v(row) += s * somenumber(omega) / somenumber(val[cols->rowstart[row]]); |
| 1800 |
} |
| 1801 |
} |
| 1802 |
|
| 1803 |
|
| 1804 |
|
| 1805 |
template <typename number> |
| 1806 |
template <typename somenumber> |
| 1807 |
void |
| 1808 |
SparseMatrix<number>::SSOR_step(Vector<somenumber> &v, |
| 1809 |
const Vector<somenumber> &b, |
| 1810 |
const number omega) const |
| 1811 |
{ |
| 1812 |
SOR_step(v, b, omega); |
| 1813 |
TSOR_step(v, b, omega); |
| 1814 |
} |
| 1815 |
|
| 1816 |
|
| 1817 |
|
| 1818 |
template <typename number> |
| 1819 |
template <typename somenumber> |
| 1820 |
void |
| 1821 |
SparseMatrix<number>::SSOR(Vector<somenumber> &dst, const number omega) const |
| 1822 |
{ |
| 1823 |
// TODO: Is this called anywhere? If so, multiplication with omega(2-omega)D |
| 1824 |
// is missing |
| 1825 |
DEAL_II_NOT_IMPLEMENTED(); |
| 1826 |
|
| 1827 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1828 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1829 |
AssertDimension(m(), n()); |
| 1830 |
Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size())); |
| 1831 |
|
| 1832 |
internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this); |
| 1833 |
|
| 1834 |
const size_type n = dst.size(); |
| 1835 |
size_type j; |
| 1836 |
somenumber s; |
| 1837 |
|
| 1838 |
for (size_type i = 0; i < n; ++i) |
| 1839 |
{ |
| 1840 |
s = 0.; |
| 1841 |
for (j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j) |
| 1842 |
{ |
| 1843 |
const size_type p = cols->colnums[j]; |
| 1844 |
if (p != SparsityPattern::invalid_entry) |
| 1845 |
{ |
| 1846 |
if (i > j) |
| 1847 |
s += somenumber(val[j]) * dst(p); |
| 1848 |
} |
| 1849 |
} |
| 1850 |
dst(i) -= s * somenumber(omega); |
| 1851 |
dst(i) /= somenumber(val[cols->rowstart[i]]); |
| 1852 |
} |
| 1853 |
|
| 1854 |
for (int i = n - 1; i >= 0; |
| 1855 |
i--) // this time, i is signed, but always positive! |
| 1856 |
{ |
| 1857 |
s = 0.; |
| 1858 |
for (j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j) |
| 1859 |
{ |
| 1860 |
const size_type p = cols->colnums[j]; |
| 1861 |
if (p != SparsityPattern::invalid_entry) |
| 1862 |
{ |
| 1863 |
if (static_cast<size_type>(i) < j) |
| 1864 |
s += somenumber(val[j]) * dst(p); |
| 1865 |
} |
| 1866 |
} |
| 1867 |
dst(i) -= s * somenumber(omega) / somenumber(val[cols->rowstart[i]]); |
| 1868 |
} |
| 1869 |
} |
| 1870 |
|
| 1871 |
|
| 1872 |
|
| 1873 |
template <typename number> |
| 1874 |
void |
| 1875 |
SparseMatrix<number>::print_formatted(std::ostream &out, |
| 1876 |
const unsigned int precision, |
| 1877 |
const bool scientific, |
| 1878 |
const unsigned int width_, |
| 1879 |
const char *zero_string, |
| 1880 |
const double denominator, |
| 1881 |
const char *separator) const |
| 1882 |
{ |
| 1883 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1884 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1885 |
|
| 1886 |
unsigned int width = width_; |
| 1887 |
|
| 1888 |
std::ios::fmtflags old_flags = out.flags(); |
| 1889 |
unsigned int old_precision = out.precision(precision); |
| 1890 |
|
| 1891 |
if (scientific) |
| 1892 |
{ |
| 1893 |
out.setf(std::ios::scientific, std::ios::floatfield); |
| 1894 |
if (width == 0u) |
| 1895 |
width = precision + 7; |
| 1896 |
} |
| 1897 |
else |
| 1898 |
{ |
| 1899 |
out.setf(std::ios::fixed, std::ios::floatfield); |
| 1900 |
if (width == 0u) |
| 1901 |
width = precision + 2; |
| 1902 |
} |
| 1903 |
|
| 1904 |
for (size_type i = 0; i < m(); ++i) |
| 1905 |
{ |
| 1906 |
for (size_type j = 0; j < n(); ++j) |
| 1907 |
if ((*cols)(i, j) != SparsityPattern::invalid_entry) |
| 1908 |
out << std::setw(width) |
| 1909 |
<< val[cols->operator()(i, j)] * number(denominator) << separator; |
| 1910 |
else |
| 1911 |
out << std::setw(width) << zero_string << separator; |
| 1912 |
out << std::endl; |
| 1913 |
}; |
| 1914 |
AssertThrow(out.fail() == false, ExcIO()); |
| 1915 |
|
| 1916 |
// reset output format |
| 1917 |
out.precision(old_precision); |
| 1918 |
out.flags(old_flags); |
| 1919 |
} |
| 1920 |
|
| 1921 |
|
| 1922 |
|
| 1923 |
template <typename number> |
| 1924 |
void |
| 1925 |
SparseMatrix<number>::print_pattern(std::ostream &out, |
| 1926 |
const double threshold) const |
| 1927 |
{ |
| 1928 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1929 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1930 |
|
| 1931 |
for (size_type i = 0; i < m(); ++i) |
| 1932 |
{ |
| 1933 |
for (size_type j = 0; j < n(); ++j) |
| 1934 |
if ((*cols)(i, j) == SparsityPattern::invalid_entry) |
| 1935 |
out << '.'; |
| 1936 |
else if (std::abs(val[cols->operator()(i, j)]) > threshold) |
| 1937 |
out << '*'; |
| 1938 |
else |
| 1939 |
out << ':'; |
| 1940 |
out << std::endl; |
| 1941 |
}; |
| 1942 |
AssertThrow(out.fail() == false, ExcIO()); |
| 1943 |
} |
| 1944 |
|
| 1945 |
|
| 1946 |
|
| 1947 |
template <typename number> |
| 1948 |
void |
| 1949 |
SparseMatrix<number>::print_as_numpy_arrays(std::ostream &out, |
| 1950 |
const unsigned int precision) const |
| 1951 |
{ |
| 1952 |
AssertThrow(out.fail() == false, ExcIO()); |
| 1953 |
boost::io::ios_flags_saver restore_flags(out); |
| 1954 |
|
| 1955 |
out.precision(precision); |
| 1956 |
|
| 1957 |
Assert(cols != nullptr, ExcNeedsSparsityPattern()); |
| 1958 |
Assert(val != nullptr, ExcNotInitialized()); |
| 1959 |
|
| 1960 |
std::vector<number> rows; |
| 1961 |
std::vector<number> columns; |
| 1962 |
std::vector<number> values; |
| 1963 |
rows.reserve(n_nonzero_elements()); |
| 1964 |
columns.reserve(n_nonzero_elements()); |
| 1965 |
values.reserve(n_nonzero_elements()); |
| 1966 |
|
| 1967 |
for (size_type i = 0; i < cols->rows; ++i) |
| 1968 |
{ |
| 1969 |
for (size_type j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j) |
| 1970 |
{ |
| 1971 |
rows.push_back(i); |
| 1972 |
columns.push_back(cols->colnums[j]); |
| 1973 |
values.push_back(val[j]); |
| 1974 |
} |
| 1975 |
} |
| 1976 |
|
| 1977 |
for (auto d : values) |
| 1978 |
out << d << ' '; |
| 1979 |
out << '\n'; |
| 1980 |
|
| 1981 |
for (auto r : rows) |
| 1982 |
out << r << ' '; |
| 1983 |
out << '\n'; |
| 1984 |
|
| 1985 |
for (auto c : columns) |
| 1986 |
out << c << ' '; |
| 1987 |
out << '\n'; |
| 1988 |
out << std::flush; |
| 1989 |
|
| 1990 |
AssertThrow(out.fail() == false, ExcIO()); |
| 1991 |
} |
| 1992 |
|
| 1993 |
|
| 1994 |
|
| 1995 |
template <typename number> |
| 1996 |
void |
| 1997 |
SparseMatrix<number>::block_write(std::ostream &out) const |
| 1998 |
{ |
| 1999 |
AssertThrow(out.fail() == false, ExcIO()); |
| 2000 |
|
| 2001 |
// first the simple objects, |
| 2002 |
// bracketed in [...] |
| 2003 |
out << '[' << max_len << "]["; |
| 2004 |
// then write out real data |
| 2005 |
out.write(reinterpret_cast<const char *>(val.get()), |
| 2006 |
reinterpret_cast<const char *>(val.get() + max_len) - |
| 2007 |
reinterpret_cast<const char *>(val.get())); |
| 2008 |
out << ']'; |
| 2009 |
|
| 2010 |
AssertThrow(out.fail() == false, ExcIO()); |
| 2011 |
} |
| 2012 |
|
| 2013 |
|
| 2014 |
|
| 2015 |
template <typename number> |
| 2016 |
void |
| 2017 |
SparseMatrix<number>::block_read(std::istream &in) |
| 2018 |
{ |
| 2019 |
AssertThrow(in.fail() == false, ExcIO()); |
| 2020 |
|
| 2021 |
char c; |
| 2022 |
|
| 2023 |
// first read in simple data |
| 2024 |
in >> c; |
| 2025 |
AssertThrow(c == '[', ExcIO()); |
| 2026 |
in >> max_len; |
| 2027 |
|
| 2028 |
in >> c; |
| 2029 |
AssertThrow(c == ']', ExcIO()); |
| 2030 |
in >> c; |
| 2031 |
AssertThrow(c == '[', ExcIO()); |
| 2032 |
|
| 2033 |
// reallocate space |
| 2034 |
val = std::make_unique<number[]>(max_len); |
| 2035 |
|
| 2036 |
// then read data |
| 2037 |
in.read(reinterpret_cast<char *>(val.get()), |
| 2038 |
reinterpret_cast<char *>(val.get() + max_len) - |
| 2039 |
reinterpret_cast<char *>(val.get())); |
| 2040 |
in >> c; |
| 2041 |
AssertThrow(c == ']', ExcIO()); |
| 2042 |
} |
| 2043 |
|
| 2044 |
|
| 2045 |
template <typename number> |
| 2046 |
void |
| 2047 |
SparseMatrix<number>::compress(VectorOperation::values) |
| 2048 |
{} |
| 2049 |
|
| 2050 |
|
| 2051 |
template <typename number> |
| 2052 |
std::size_t |
| 2053 |
SparseMatrix<number>::memory_consumption() const |
| 2054 |
{ |
| 2055 |
return max_len * static_cast<std::size_t>(sizeof(number)) + sizeof(*this); |
| 2056 |
} |
| 2057 |
|
| 2058 |
|
| 2059 |
DEAL_II_NAMESPACE_CLOSE |
| 2060 |
|
| 2061 |
#endif |