Debian Codegraph @

include/deal.II/lac/sparse_direct.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2001 - 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 #ifndef dealii_sparse_direct_h
16 #define dealii_sparse_direct_h
17
18
19
20 #include <deal.II/base/config.h>
21
22 #include <deal.II/base/enable_observer_pointer.h>
23 #include <deal.II/base/exceptions.h>
24
25 #include <deal.II/lac/block_sparse_matrix.h>
26 #include <deal.II/lac/sparse_matrix.h>
27 #include <deal.II/lac/sparse_matrix_ez.h>
28 #include <deal.II/lac/vector.h>
29
30 #ifdef DEAL_II_WITH_UMFPACK
31 # include <umfpack.h>
32 #endif
33
34 #ifdef DEAL_II_WITH_MUMPS
35 # include <dmumps_c.h>
36 #endif
37
38 #ifdef DEAL_II_WITH_TRILINOS
39 # include <deal.II/lac/trilinos_sparse_matrix.h>
40 # include <deal.II/lac/trilinos_vector.h>
41 #endif
42
43 #ifdef DEAL_II_WITH_PETSC
44 # include <deal.II/lac/petsc_sparse_matrix.h>
45 # include <deal.II/lac/petsc_vector.h>
46 #endif
47
48 DEAL_II_NAMESPACE_OPEN
49
50 namespace types
51 {
52 /**
53 * Index type for UMFPACK. SuiteSparse_long has to be used here for the
54 * Windows 64 build.
55 */
56 #ifdef SuiteSparse_long
57 using suitesparse_index = SuiteSparse_long;
58 #else
59 using suitesparse_index = long int;
60 #endif
61
62 #ifdef DEAL_II_WITH_MUMPS
63 using mumps_index = MUMPS_INT;
64 using mumps_nnz = MUMPS_INT8;
65 #else
66 using mumps_index = int;
67 using mumps_nnz = std::size_t;
68 #endif
69
70
71 } // namespace types
72
73 /**
74 * This class provides an interface to the sparse direct solver UMFPACK, which
75 * is part of the SuiteSparse library (see <a
76 * href="http://faculty.cse.tamu.edu/davis/suitesparse.html">this link</a>).
77 * UMFPACK is a set of routines for solving non-symmetric sparse linear
78 * systems, Ax=b, using the Unsymmetric-pattern MultiFrontal method and direct
79 * sparse LU factorization. Matrices may have symmetric or unsymmetric
80 * sparsity patterns, and may have unsymmetric entries. The use of this class
81 * is explained in the step-22 and step-29
82 * tutorial programs.
83 *
84 * This matrix class implements the usual interface of preconditioners, that
85 * is a function initialize(const SparseMatrix<double>&matrix,const
86 * AdditionalData) for initializing and the whole set of vmult() functions
87 * common to all matrices. Implemented here are only vmult() and vmult_add(),
88 * which perform multiplication with the inverse matrix. Furthermore, this
89 * class provides an older interface, consisting of the functions factorize()
90 * and solve(). Both interfaces are interchangeable.
91 *
92 * @note This class exists if the <a
93 * href="http://faculty.cse.tamu.edu/davis/suitesparse.html">UMFPACK</a>
94 * interface was not explicitly disabled during configuration.
95 *
96 * @note UMFPACK has its own license, independent of that of deal.II. If you
97 * want to use the UMFPACK you have to accept that license. It is linked to
98 * from the deal.II ReadMe file. UMFPACK is included courtesy of its author,
99 * <a href="http://faculty.cse.tamu.edu/davis/welcome.html">Timothy
100 * A. Davis</a>.
101 *
102 *
103 * <h4>Instantiations</h4>
104 *
105 * There are instantiations of this class for SparseMatrix<double>,
106 * SparseMatrix<float>, SparseMatrixEZ<float>, SparseMatrixEZ<double>,
107 * BlockSparseMatrix<double>, and BlockSparseMatrix<float>.
108 *
109 * This class is not instantiated for the matrix types in namespace
110 * PETScWrappers or TrilinosWrappers. However, PETScWrappers::SparseDirectMUMPS
111 * can be used for PETSc matrices, and in fact even works for parallel
112 * computations.
113 *
114 * @ingroup Solvers Preconditioners
115 */
116 class SparseDirectUMFPACK : public EnableObserverPointer
117 {
118 public:
119 /**
120 * Declare type for container size.
121 */
122 using size_type = types::global_dof_index;
123
124 /**
125 * Dummy class needed for the usual initialization interface of
126 * preconditioners.
127 */
128 class AdditionalData
129 {};
130
131
132 /**
133 * Constructor. See the documentation of this class for the meaning of the
134 * parameters to this function.
135 */
136 SparseDirectUMFPACK();
137
138 /**
139 * Destructor.
140 */
141 ~SparseDirectUMFPACK() override;
142
143 /**
144 * @name Setting up a sparse factorization
145 */
146 /**
147 * @{
148 */
149
150 /**
151 * This function does nothing. It is only here to provide a interface
152 * consistent with other sparse direct solvers.
153 */
154 void
155 initialize(const SparsityPattern &sparsity_pattern);
156
157 /**
158 * Factorize the matrix. This function may be called multiple times for
159 * different matrices, after the object of this class has been initialized
160 * for a certain sparsity pattern. You may therefore save some computing
161 * time if you want to invert several matrices with the same sparsity
162 * pattern. However, note that the bulk of the computing time is actually
163 * spent in the factorization, so this functionality may not always be of
164 * large benefit.
165 *
166 * In contrast to the other direct solver classes, the initialization method
167 * does nothing. Therefore initialize is not automatically called by this
168 * method, when the initialization step has not been performed yet.
169 *
170 * This function copies the contents of the matrix into its own storage; the
171 * matrix can therefore be deleted after this operation, even if subsequent
172 * solves are required.
173 */
174 template <class Matrix>
175 void
176 factorize(const Matrix &matrix);
177
178 /**
179 * Initialize memory and call SparseDirectUMFPACK::factorize.
180 */
181 template <class Matrix>
182 void
183 initialize(const Matrix &matrix,
184 const AdditionalData additional_data = AdditionalData());
185
186 /**
187 * @}
188 */
189
190 /**
191 * @name Functions that represent the inverse of a matrix
192 */
193 /**
194 * @{
195 */
196
197 /**
198 * Preconditioner interface function. Usually, given the source vector, this
199 * method returns an approximate solution of <i>Ax = b</i>. As this class
200 * provides a wrapper to a direct solver, here it is actually the exact
201 * solution (exact within the range of numerical accuracy of course).
202 *
203 * In other words, this function actually multiplies with the exact inverse
204 * of the matrix, $A^{-1}$.
205 */
206 void
207 vmult(Vector<double> &dst, const Vector<double> &src) const;
208
209 /**
210 * Same as before, but for block vectors.
211 */
212 void
213 vmult(BlockVector<double> &dst, const BlockVector<double> &src) const;
214
215 /**
216 * Same as before, but uses the transpose of the matrix, i.e. this function
217 * multiplies with $A^{-T}$.
218 */
219 void
220 Tvmult(Vector<double> &dst, const Vector<double> &src) const;
221
222 /**
223 * Same as before, but for block vectors
224 */
225 void
226 Tvmult(BlockVector<double> &dst, const BlockVector<double> &src) const;
227
228 /**
229 * Return the dimension of the codomain (or range) space. Note that the
230 * matrix is of dimension $m \times n$.
231 */
232 size_type
233 m() const;
234
235 /**
236 * Return the dimension of the domain space. Note that the matrix is of
237 * dimension $m \times n$.
238 */
239 size_type
240 n() const;
241
242 /**
243 * @}
244 */
245
246 /**
247 * @name Functions that solve linear systems
248 */
249 /**
250 * @{
251 */
252
253 /**
254 * Solve for a certain right hand side vector. This function may be called
255 * multiple times for different right hand side vectors after the matrix has
256 * been factorized. This yields substantial savings in computing time, since
257 * the actual solution is fast, compared to the factorization of the matrix.
258 *
259 * The solution will be returned in place of the right hand side vector.
260 *
261 * @param[in,out] rhs_and_solution A vector that contains the right hand side
262 * $b$ of a linear system $Ax=b$ upon calling this function, and that
263 * contains the solution $x$ of the linear system after calling this
264 * function.
265 * @param[in] transpose If set to true, this function solves the linear
266 * $A^T x = b$ instead of $Ax=b$.
267 *
268 * @pre You need to call factorize() before this function can be called.
269 */
270 void
271 solve(Vector<double> &rhs_and_solution, const bool transpose = false) const;
272
273 /**
274 * Like the previous function, but for a complex-valued right hand side
275 * and solution vector.
276 *
277 * If the matrix that was previously factorized had complex-valued entries,
278 * then the `rhs_and_solution` vector will, upon return from this function,
279 * simply contain the solution of the linear system $Ax=b$. If the matrix
280 * was real-valued, then this is also true, but the solution will simply
281 * be computed by applying the factorized $A^{-1}$ to both the
282 * real and imaginary parts of the right hand side vector.
283 */
284 void
285 solve(Vector<std::complex<double>> &rhs_and_solution,
286 const bool transpose = false) const;
287
288 /**
289 * Same as before, but for block vectors.
290 */
291 void
292 solve(BlockVector<double> &rhs_and_solution,
293 const bool transpose = false) const;
294
295 /**
296 * Same as before, but for complex-valued block vectors.
297 */
298 void
299 solve(BlockVector<std::complex<double>> &rhs_and_solution,
300 const bool transpose = false) const;
301
302 /**
303 * Call the two functions factorize() and solve() in that order, i.e.
304 * perform the whole solution process for the given right hand side vector.
305 *
306 * The solution will be returned in place of the right hand side vector.
307 */
308 template <class Matrix>
309 void
310 solve(const Matrix &matrix,
311 Vector<double> &rhs_and_solution,
312 const bool transpose = false);
313
314 /**
315 * Same as before, but for complex-valued solution vectors.
316 */
317 template <class Matrix>
318 void
319 solve(const Matrix &matrix,
320 Vector<std::complex<double>> &rhs_and_solution,
321 const bool transpose = false);
322
323 /**
324 * Same as before, but for block vectors.
325 */
326 template <class Matrix>
327 void
328 solve(const Matrix &matrix,
329 BlockVector<double> &rhs_and_solution,
330 const bool transpose = false);
331
332 /**
333 * Same as before, but for complex-valued block vectors.
334 */
335 template <class Matrix>
336 void
337 solve(const Matrix &matrix,
338 BlockVector<std::complex<double>> &rhs_and_solution,
339 const bool transpose = false);
340
341 /**
342 * @}
343 */
344
345 /**
346 * One of the UMFPack routines threw an error. The error code is included in
347 * the output and can be looked up in the UMFPack user manual. The name of
348 * the routine is included for reference.
349 */
350 DeclException2(
351 ExcUMFPACKError,
352 std::string,
353 int,
354 << "UMFPACK routine " << arg1 << " returned error status " << arg2 << '.'
355 << "\n\n"
356 << ("A complete list of error codes can be found in the file "
357 "<bundled/umfpack/UMFPACK/Include/umfpack.h>."
358 "\n\n"
359 "That said, the two most common errors that can happen are "
360 "that your matrix cannot be factorized because it is "
361 "rank deficient, and that UMFPACK runs out of memory "
362 "because your problem is too large."
363 "\n\n"
364 "The first of these cases most often happens if you "
365 "forget terms in your bilinear form necessary to ensure "
366 "that the matrix has full rank, or if your equation has a "
367 "spatially variable coefficient (or nonlinearity) that is "
368 "supposed to be strictly positive but, for whatever "
369 "reasons, is negative or zero. In either case, you probably "
370 "want to check your assembly procedure. Similarly, a "
371 "matrix can be rank deficient if you forgot to apply the "
372 "appropriate boundary conditions. For example, the "
373 "Laplace equation for a problem where only Neumann boundary "
374 "conditions are posed (or where you forget to apply Dirichlet "
375 "boundary conditions) has exactly one eigenvalue equal to zero "
376 "and its rank is therefore deficient by one. Finally, the matrix "
377 "may be rank deficient because you are using a quadrature "
378 "formula with too few quadrature points."
379 "\n\n"
380 "The other common situation is that you run out of memory. "
381 "On a typical laptop or desktop, it should easily be possible "
382 "to solve problems with 100,000 unknowns in 2d. If you are "
383 "solving problems with many more unknowns than that, in "
384 "particular if you are in 3d, then you may be running out "
385 "of memory and you will need to consider iterative "
386 "solvers instead of the direct solver employed by "
387 "UMFPACK."));
388
389 private:
390 /**
391 * The dimension of the range space, i.e., the number of rows of the matrix.
392 */
393 size_type n_rows;
394
395 /**
396 * The dimension of the domain space, i.e., the number of columns of the
397 * matrix.
398 */
399 size_type n_cols;
400
401 /**
402 * The UMFPACK routines allocate objects in which they store information
403 * about symbolic and numeric values of the decomposition. The actual data
404 * type of these objects is opaque, and only passed around as void pointers.
405 */
406 void *symbolic_decomposition;
407 void *numeric_decomposition;
408
409 /**
410 * Free all memory that hasn't been freed yet.
411 */
412 void
413 clear();
414
415 /**
416 * Make sure that the arrays Ai and Ap are sorted in each row. UMFPACK wants
417 * it this way. We need to have three versions of this function, one for the
418 * usual SparseMatrix, one for the SparseMatrixEZ, and one for the
419 * BlockSparseMatrix classes
420 */
421 template <typename number>
422 void
423 sort_arrays(const SparseMatrixEZ<number> &);
424
425 template <typename number>
426 void
427 sort_arrays(const SparseMatrix<number> &);
428
429 template <typename number>
430 void
431 sort_arrays(const BlockSparseMatrix<number> &);
432
433 /**
434 * The arrays in which we store the data for the solver. These are documented
435 * in the descriptions of the umfpack_*_symbolic() and umfpack_*_numeric()
436 * functions, but in short:
437 * - `Ap` is the array saying which row starts where in `Ai`
438 * - `Ai` is the array that stores the column indices of nonzero entries
439 * - `Ax` is the array that stores the values of nonzero entries; if the
440 * matrix is complex-valued, then it stores the real parts
441 * - `Az` is the array that stores the imaginary parts of nonzero entries,
442 * and is used only if the matrix is complex-valued.
443 */
444 std::vector<types::suitesparse_index> Ap;
445 std::vector<types::suitesparse_index> Ai;
446 std::vector<double> Ax;
447 std::vector<double> Az;
448
449 /**
450 * Control and work arrays for the solver routines.
451 */
452 std::vector<double> control;
453 };
454
455
456
457 /**
458 * This class provides an interface to the parallel sparse direct solver <a
459 * href="https://mumps-solver.org">MUMPS</a>. MUMPS is direct method based on
460 * a multifrontal approach, which performs a direct LU factorization. The
461 * matrix coming in may have either symmetric or nonsymmetric sparsity
462 * pattern.
463 *
464 * @note This class is useable if and only if a working installation of <a
465 * href="https://mumps-solver.org">MUMPS</a> exists on your system and was
466 * detected during configuration of <code>deal.II</code>.
467 *
468 * <h4>Instantiations</h4>
469 *
470 * There are instantiations of this class for SparseMatrix<double>,
471 * SparseMatrix<float>, BlockSparseMatrix<double>, and
472 * BlockSparseMatrix<float>.
473 *
474 * @ingroup Solvers Preconditioners
475 */
476 class SparseDirectMUMPS : public EnableObserverPointer
477 {
478 public:
479 /**
480 * Declare type for container size.
481 */
482 using size_type = types::global_dof_index;
483
484 /**
485 * The AdditionalData contains data for controlling the MUMPS execution.
486 */
487 struct AdditionalData
488 {
489 /**
490 * Struct that contains the data for the Block Low-Rank approximation.
491 */
492 struct BlockLowRank
493 {
494 BlockLowRank(const bool blr_ucfs = false,
495 const double lowrank_threshold = 1e-8)
496 : blr_ucfs(blr_ucfs)
497 , lowrank_threshold(lowrank_threshold)
498 {}
499
500
501 /**
502 * If true, the Block Low-Rank approximation is used with the UCFS
503 * algorithm, an algorithm with higher compression than the standard one.
504 */
505 bool blr_ucfs;
506
507 /**
508 * Threshold for the low-rank truncation of the blocks.
509 */
510 double lowrank_threshold;
511 };
512
513 /**
514 * Construct a new Additional Data object with the given parameters.
515 */
516 AdditionalData(const bool output_details = false,
517 const bool error_statistics = false,
518 const bool symmetric = false,
519 const bool posdef = false,
520 const bool blr_factorization = false,
521 const BlockLowRank &blr = BlockLowRank())
522 : output_details(output_details)
523 , error_statistics(error_statistics)
524 , symmetric(symmetric)
525 , posdef(posdef)
526 , blr_factorization(blr_factorization)
527 , blr(blr)
528 {}
529
530 /**
531 * If true, the MUMPS solver will print out details of the execution.
532 */
533 bool output_details;
534
535 /**
536 * If true, the MUMPS solver will print out error statistics.
537 */
538 bool error_statistics;
539
540 /**
541 * Use symmetric factorization.
542 *
543 * This is only possible if the matrix is symmetric, but no checks are
544 * performed to ensure that this is actually the case. The solver will
545 * likely break or produce incorrect results if the matrix is not symmetric,
546 * and this option is set to true.
547 */
548 bool symmetric;
549
550 /**
551 * Use the positive definite factorization.
552 *
553 * This is only possible if the matrix is symmetric and positive definite,
554 * but no checks are performed to ensure that this is actually the case. The
555 * solver will likely break or produce incorrect results if the matrix is
556 * not symmetric and positive definite, and this option is set to true.
557 */
558 bool posdef;
559
560 /**
561 * Use the Block Low-Rank factorization.
562 */
563 bool blr_factorization;
564
565 /**
566 * Data for the Block Low-Rank approximation.
567 */
568 BlockLowRank blr;
569 };
570
571 /**
572 * Constructor, takes an MPI_Comm which defaults to MPI_COMM_WORLD and an
573 * <tt>AdditionalData</tt> to control MUMPS execution.
574 */
575 SparseDirectMUMPS(const AdditionalData &additional_data = AdditionalData(),
576 const MPI_Comm &communicator = MPI_COMM_WORLD);
577
578 /**
579 * Destructor
580 */
581 ~SparseDirectMUMPS();
582
583 /**
584 * Exception raised if the initialize() function is called more than once.
585 */
586 DeclException0(ExcInitializeAlreadyCalled);
587
588 /**
589 * This function computes the LU factorization
590 * of the system's matrix <tt>matrix</tt> with the options given in the
591 * constructor's <tt>AdditionalData</tt>.
592 */
593 template <class Matrix>
594 void
595 initialize(const Matrix &matrix);
596
597 /**
598 * Apply the inverse of the matrix to the input vector <tt>src</tt> and store
599 * the solution in the output vector <tt>dst</tt>.
600 */
601 template <typename VectorType>
602 void
603 vmult(VectorType &dst, const VectorType &src) const;
604
605
606 /**
607 * Apply the inverse of the transposed matrix to the input vector <tt>src</tt>
608 * and store the solution in the output vector <tt>dst</tt>.
609 */
610 template <typename VectorType>
611 void
612 Tvmult(VectorType &, const VectorType &src) const;
613
614 /**
615 * Return the ICNTL integer array from MUMPS.
616 *
617 * The ICNTL array contains integer control parameters for the MUMPS solver.
618 * Keep in mind that MUMPS is a fortran library and the documentation refers
619 * to indices into this array starting from one rather than from zero. To
620 * select the correct index one can use a macro like this:
621 *
622 * `#define ICNTL(I) icntl[(I)-1]`
623 *
624 * The MUMPS documentation describes each parameter of the array. Be aware
625 * that ownership of the array remains in the current class rather than with
626 * the caller of this function.
627 */
628 int *
629 get_icntl();
630
631 private:
632 #ifdef DEAL_II_WITH_MUMPS
633 mutable DMUMPS_STRUC_C id;
634
635 #endif // DEAL_II_WITH_MUMPS
636
637 /**
638 * The actual values of the matrix.
639 *
640 * a[k] is the value of the matrix entry (i,j) if irn[k] == i and jcn[k] == j.
641 */
642 std::unique_ptr<double[]> a;
643
644 /**
645 * The right-hand side vector.
646 */
647 mutable std::vector<double> rhs;
648
649 /**
650 * Local to global index mapping for the right-hand side vector.
651 */
652 mutable std::vector<types::mumps_index> irhs_loc;
653
654 /**
655 * irn contains the row indices of the non-zero entries of the matrix.
656 */
657 std::unique_ptr<types::mumps_index[]> irn;
658
659 /**
660 * jcn contains the column indices of the non-zero entries of the matrix.
661 */
662 std::unique_ptr<types::mumps_index[]> jcn;
663
664 /**
665 * The number of rows of the matrix. The matrix is square.
666 */
667 types::global_dof_index n;
668
669 /**
670 * Number of non-zero entries in the matrix.
671 */
672 types::mumps_nnz nnz;
673
674 /**
675 * IndexSet storing the locally owned rows of the matrix.
676 */
677 IndexSet locally_owned_rows;
678
679 /**
680 * This function initializes a MUMPS instance and hands over the system's
681 * matrix <tt>matrix</tt>.
682 */
683 template <class Matrix>
684 void
685 initialize_matrix(const Matrix &matrix);
686
687 /**
688 * Copy the computed solution into the solution vector.
689 */
690 void
691 copy_solution(Vector<double> &vector) const;
692
693 /**
694 * Copy the right-hand side vector into the MUMPS instance.
695 */
696 void
697 copy_rhs_to_mumps(const Vector<double> &rhs) const;
698
699 /**
700 * Struct that holds the additional data for the MUMPS solver.
701 */
702 AdditionalData additional_data;
703
704 /**
705 * MPI_Comm object for the MUMPS solver.
706 */
707 const MPI_Comm mpi_communicator;
708 };
709
710 DEAL_II_NAMESPACE_CLOSE
711
712 #endif // dealii_sparse_direct_h