step-22.h

Go to the documentation of this file.

,
 *                                    const unsigned int /*component*/) const
 *   {
 *     return 0;
 *   }
 * 
 * 
 *   template <int dim>
 *   void RightHandSide<dim>::vector_value(const Point<dim> &p,
 *                                         Vector<double> &  values) const
 *   {
 *     for (unsigned int c = 0; c < this->n_components; ++c)
 *       values(c) = RightHandSide<dim>::value(p, c);
 *   }
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="Linearsolversandpreconditioners"></a> 
 * <h3>Linear solvers and preconditioners</h3>
 * 

 * 
 * The linear solvers and preconditioners are discussed extensively in the
 * introduction. Here, we create the respective objects that will be used.
 * 

 * 
 * 
 * <a name="ThecodeInverseMatrixcodeclasstemplate"></a> 
 * <h4>The <code>InverseMatrix</code> class template</h4>
 * The <code>InverseMatrix</code> class represents the data structure for an
 * inverse matrix. Unlike @ref step_20 "step-20", we implement this with a class instead of
 * the helper function inverse_linear_operator() we will apply this class to
 * different kinds of matrices that will require different preconditioners
 * (in @ref step_20 "step-20" we only used a non-identity preconditioner for the mass
 * matrix). The types of matrix and preconditioner are passed to this class
 * via template parameters, and matrix and preconditioner objects of these
 * types will then be passed to the constructor when an
 * <code>InverseMatrix</code> object is created. The member function
 * <code>vmult</code> is obtained by solving a linear system:
 * 
 * @code
 *   template <class MatrixType, class PreconditionerType>
 *   class InverseMatrix : public Subscriptor
 *   {
 *   public:
 *     InverseMatrix(const MatrixType &        m,
 *                   const PreconditionerType &preconditioner);
 * 
 *     void vmult(Vector<double> &dst, const Vector<double> &src) const;
 * 
 *   private:
 *     const SmartPointer<const MatrixType>         matrix;
 *     const SmartPointer<const PreconditionerType> preconditioner;
 *   };
 * 
 * 
 *   template <class MatrixType, class PreconditionerType>
 *   InverseMatrix<MatrixType, PreconditionerType>::InverseMatrix(
 *     const MatrixType &        m,
 *     const PreconditionerType &preconditioner)
 *     : matrix(&m)
 *     , preconditioner(&preconditioner)
 *   {}
 * 
 * 
 * @endcode
 * 
 * This is the implementation of the <code>vmult</code> function.
 * 

 * 
 * In this class we use a rather large tolerance for the solver control. The
 * reason for this is that the function is used very frequently, and hence,
 * any additional effort to make the residual in the CG solve smaller makes
 * the solution more expensive. Note that we do not only use this class as a
 * preconditioner for the Schur complement, but also when forming the
 * inverse of the Laplace matrix &ndash; which is hence directly responsible
 * for the accuracy of the solution itself, so we can't choose a too large
 * tolerance, either.
 * 
 * @code
 *   template <class MatrixType, class PreconditionerType>
 *   void InverseMatrix<MatrixType, PreconditionerType>::vmult(
 *     Vector<double> &      dst,
 *     const Vector<double> &src) const
 *   {
 *     SolverControl            solver_control(src.size(), 1e-6 * src.l2_norm());
 *     SolverCG<Vector<double>> cg(solver_control);
 * 
 *     dst = 0;
 * 
 *     cg.solve(*matrix, dst, src, *preconditioner);
 *   }
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="ThecodeSchurComplementcodeclasstemplate"></a> 
 * <h4>The <code>SchurComplement</code> class template</h4>
 * 

 * 
 * This class implements the Schur complement discussed in the introduction.
 * It is in analogy to @ref step_20 "step-20".  Though, we now call it with a template
 * parameter <code>PreconditionerType</code> in order to access that when
 * specifying the respective type of the inverse matrix class. As a
 * consequence of the definition above, the declaration
 * <code>InverseMatrix</code> now contains the second template parameter for
 * a preconditioner class as above, which affects the
 * <code>SmartPointer</code> object <code>m_inverse</code> as well.
 * 
 * @code
 *   template <class PreconditionerType>
 *   class SchurComplement : public Subscriptor
 *   {
 *   public:
 *     SchurComplement(
 *       const BlockSparseMatrix<double> &system_matrix,
 *       const InverseMatrix<SparseMatrix<double>, PreconditionerType> &A_inverse);
 * 
 *     void vmult(Vector<double> &dst, const Vector<double> &src) const;
 * 
 *   private:
 *     const SmartPointer<const BlockSparseMatrix<double>> system_matrix;
 *     const SmartPointer<
 *       const InverseMatrix<SparseMatrix<double>, PreconditionerType>>
 *       A_inverse;
 * 
 *     mutable Vector<double> tmp1, tmp2;
 *   };
 * 
 * 
 * 
 *   template <class PreconditionerType>
 *   SchurComplement<PreconditionerType>::SchurComplement(
 *     const BlockSparseMatrix<double> &system_matrix,
 *     const InverseMatrix<SparseMatrix<double>, PreconditionerType> &A_inverse)
 *     : system_matrix(&system_matrix)
 *     , A_inverse(&A_inverse)
 *     , tmp1(system_matrix.block(0, 0).m())
 *     , tmp2(system_matrix.block(0, 0).m())
 *   {}
 * 
 * 
 *   template <class PreconditionerType>
 *   void
 *   SchurComplement<PreconditionerType>::vmult(Vector<double> &      dst,
 *                                              const Vector<double> &src) const
 *   {
 *     system_matrix->block(0, 1).vmult(tmp1, src);
 *     A_inverse->vmult(tmp2, tmp1);
 *     system_matrix->block(1, 0).vmult(dst, tmp2);
 *   }
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="StokesProblemclassimplementation"></a> 
 * <h3>StokesProblem class implementation</h3>
 * 

 * 
 * 
 * <a name="StokesProblemStokesProblem"></a> 
 * <h4>StokesProblem::StokesProblem</h4>
 * 

 * 
 * The constructor of this class looks very similar to the one of
 * @ref step_20 "step-20". The constructor initializes the variables for the polynomial
 * degree, triangulation, finite element system and the dof handler. The
 * underlying polynomial functions are of order <code>degree+1</code> for
 * the vector-valued velocity components and of order <code>degree</code>
 * for the pressure.  This gives the LBB-stable element pair
 * @f$Q_{degree+1}^d\times Q_{degree}@f$, often referred to as the Taylor-Hood
 * element.
 *   

 * 
 * Note that we initialize the triangulation with a MeshSmoothing argument,
 * which ensures that the refinement of cells is done in a way that the
 * approximation of the PDE solution remains well-behaved (problems arise if
 * grids are too unstructured), see the documentation of
 * <code>Triangulation::MeshSmoothing</code> for details.
 * 
 * @code
 *   template <int dim>
 *   StokesProblem<dim>::StokesProblem(const unsigned int degree)
 *     : degree(degree)
 *     , triangulation(Triangulation<dim>::maximum_smoothing)
 *     , fe(FE_Q<dim>(degree + 1), dim, FE_Q<dim>(degree), 1)
 *     , dof_handler(triangulation)
 *   {}
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="StokesProblemsetup_dofs"></a> 
 * <h4>StokesProblem::setup_dofs</h4>
 * 

 * 
 * Given a mesh, this function associates the degrees of freedom with it and
 * creates the corresponding matrices and vectors. At the beginning it also
 * releases the pointer to the preconditioner object (if the shared pointer
 * pointed at anything at all at this point) since it will definitely not be
 * needed any more after this point and will have to be re-computed after
 * assembling the matrix, and unties the sparse matrices from their sparsity
 * pattern objects.
 *   

 * 
 * We then proceed with distributing degrees of freedom and renumbering
 * them: In order to make the ILU preconditioner (in 3D) work efficiently,
 * it is important to enumerate the degrees of freedom in such a way that it
 * reduces the bandwidth of the matrix, or maybe more importantly: in such a
 * way that the ILU is as close as possible to a real LU decomposition. On
 * the other hand, we need to preserve the block structure of velocity and
 * pressure already seen in @ref step_20 "step-20" and @ref step_21 "step-21". This is done in two
 * steps: First, all dofs are renumbered to improve the ILU and then we
 * renumber once again by components. Since
 * <code>DoFRenumbering::component_wise</code> does not touch the
 * renumbering within the individual blocks, the basic renumbering from the
 * first step remains. As for how the renumber degrees of freedom to improve
 * the ILU: deal.II has a number of algorithms that attempt to find
 * orderings to improve ILUs, or reduce the bandwidth of matrices, or
 * optimize some other aspect. The DoFRenumbering namespace shows a
 * comparison of the results we obtain with several of these algorithms
 * based on the testcase discussed here in this tutorial program. Here, we
 * will use the traditional Cuthill-McKee algorithm already used in some of
 * the previous tutorial programs.  In the <a href="#improved-ilu">section
 * on improved ILU</a> we're going to discuss this issue in more detail.
 * 

 * 
 * There is one more change compared to previous tutorial programs: There is
 * no reason in sorting the <code>dim</code> velocity components
 * individually. In fact, rather than first enumerating all @f$x@f$-velocities,
 * then all @f$y@f$-velocities, etc, we would like to keep all velocities at the
 * same location together and only separate between velocities (all
 * components) and pressures. By default, this is not what the
 * DoFRenumbering::component_wise function does: it treats each vector
 * component separately; what we have to do is group several components into
 * "blocks" and pass this block structure to that function. Consequently, we
 * allocate a vector <code>block_component</code> with as many elements as
 * there are components and describe all velocity components to correspond
 * to block 0, while the pressure component will form block 1:
 * 
 * @code
 *   template <int dim>
 *   void StokesProblem<dim>::setup_dofs()
 *   {
 *     A_preconditioner.reset();
 *     system_matrix.clear();
 *     preconditioner_matrix.clear();
 * 
 *     dof_handler.distribute_dofs(fe);
 *     DoFRenumbering::Cuthill_McKee(dof_handler);
 * 
 *     std::vector<unsigned int> block_component(dim + 1, 0);
 *     block_component[dim] = 1;
 *     DoFRenumbering::component_wise(dof_handler, block_component);
 * 
 * @endcode
 * 
 * Now comes the implementation of Dirichlet boundary conditions, which
 * should be evident after the discussion in the introduction. All that
 * changed is that the function already appears in the setup functions,
 * whereas we were used to see it in some assembly routine. Further down
 * below where we set up the mesh, we will associate the top boundary
 * where we impose Dirichlet boundary conditions with boundary indicator
 * 1.  We will have to pass this boundary indicator as second argument to
 * the function below interpolating boundary values.  There is one more
 * thing, though.  The function describing the Dirichlet conditions was
 * defined for all components, both velocity and pressure. However, the
 * Dirichlet conditions are to be set for the velocity only.  To this end,
 * we use a ComponentMask that only selects the velocity components. The
 * component mask is obtained from the finite element by specifying the
 * particular components we want. Since we use adaptively refined grids,
 * the affine constraints object needs to be first filled with hanging node
 * constraints generated from the DoF handler. Note the order of the two
 * functions &mdash; we first compute the hanging node constraints, and
 * then insert the boundary values into the constraints object. This makes
 * sure that we respect H<sup>1</sup> conformity on boundaries with
 * hanging nodes (in three space dimensions), where the hanging node needs
 * to dominate the Dirichlet boundary values.
 * 
 * @code
 *     {
 *       constraints.clear();
 * 
 *       FEValuesExtractors::Vector velocities(0);
 *       DoFTools::make_hanging_node_constraints(dof_handler, constraints);
 *       VectorTools::interpolate_boundary_values(dof_handler,
 *                                                1,
 *                                                BoundaryValues<dim>(),
 *                                                constraints,
 *                                                fe.component_mask(velocities));
 *     }
 * 
 *     constraints.close();
 * 
 * @endcode
 * 
 * In analogy to @ref step_20 "step-20", we count the dofs in the individual components.
 * We could do this in the same way as there, but we want to operate on
 * the block structure we used already for the renumbering: The function
 * <code>DoFTools::count_dofs_per_fe_block</code> does the same as
 * <code>DoFTools::count_dofs_per_fe_component</code>, but now grouped as
 * velocity and pressure block via <code>block_component</code>.
 * 
 * @code
 *     const std::vector<types::global_dof_index> dofs_per_block =
 *       DoFTools::count_dofs_per_fe_block(dof_handler, block_component);
 *     const unsigned int n_u = dofs_per_block[0];
 *     const unsigned int n_p = dofs_per_block[1];
 * 
 *     std::cout << "   Number of active cells: " << triangulation.n_active_cells()
 *               << std::endl
 *               << "   Number of degrees of freedom: " << dof_handler.n_dofs()
 *               << " (" << n_u << '+' << n_p << ')' << std::endl;
 * 
 * @endcode
 * 
 * The next task is to allocate a sparsity pattern for the system matrix we
 * will create and one for the preconditioner matrix. We could do this in
 * the same way as in @ref step_20 "step-20", i.e. directly build an object of type
 * SparsityPattern through DoFTools::make_sparsity_pattern. However, there
 * is a major reason not to do so:
 * In 3D, the function DoFTools::max_couplings_between_dofs yields a
 * conservative but rather large number for the coupling between the
 * individual dofs, so that the memory initially provided for the creation
 * of the sparsity pattern of the matrix is far too much -- so much actually
 * that the initial sparsity pattern won't even fit into the physical memory
 * of most systems already for moderately-sized 3D problems, see also the
 * discussion in @ref step_18 "step-18". Instead, we first build temporary objects that use
 * a different data structure that doesn't require allocating more memory
 * than necessary but isn't suitable for use as a basis of SparseMatrix or
 * BlockSparseMatrix objects; in a second step we then copy these objects
 * into objects of type BlockSparsityPattern. This is entirely analogous to
 * what we already did in @ref step_11 "step-11" and @ref step_18 "step-18". In particular, we make use of
 * the fact that we will never write into the @f$(1,1)@f$ block of the system
 * matrix and that this is the only block to be filled for the
 * preconditioner matrix.
 *     

 * 
 * All this is done inside new scopes, which means that the memory of
 * <code>dsp</code> will be released once the information has been copied to
 * <code>sparsity_pattern</code>.
 * 
 * @code
 *     {
 *       BlockDynamicSparsityPattern dsp(2, 2);
 * 
 *       dsp.block(0, 0).reinit(n_u, n_u);
 *       dsp.block(1, 0).reinit(n_p, n_u);
 *       dsp.block(0, 1).reinit(n_u, n_p);
 *       dsp.block(1, 1).reinit(n_p, n_p);
 * 
 *       dsp.collect_sizes();
 * 
 *       Table<2, DoFTools::Coupling> coupling(dim + 1, dim + 1);
 * 
 *       for (unsigned int c = 0; c < dim + 1; ++c)
 *         for (unsigned int d = 0; d < dim + 1; ++d)
 *           if (!((c == dim) && (d == dim)))
 *             coupling[c][d] = DoFTools::always;
 *           else
 *             coupling[c][d] = DoFTools::none;
 * 
 *       DoFTools::make_sparsity_pattern(
 *         dof_handler, coupling, dsp, constraints, false);
 * 
 *       sparsity_pattern.copy_from(dsp);
 *     }
 * 
 *     {
 *       BlockDynamicSparsityPattern preconditioner_dsp(2, 2);
 * 
 *       preconditioner_dsp.block(0, 0).reinit(n_u, n_u);
 *       preconditioner_dsp.block(1, 0).reinit(n_p, n_u);
 *       preconditioner_dsp.block(0, 1).reinit(n_u, n_p);
 *       preconditioner_dsp.block(1, 1).reinit(n_p, n_p);
 * 
 *       preconditioner_dsp.collect_sizes();
 * 
 *       Table<2, DoFTools::Coupling> preconditioner_coupling(dim + 1, dim + 1);
 * 
 *       for (unsigned int c = 0; c < dim + 1; ++c)
 *         for (unsigned int d = 0; d < dim + 1; ++d)
 *           if (((c == dim) && (d == dim)))
 *             preconditioner_coupling[c][d] = DoFTools::always;
 *           else
 *             preconditioner_coupling[c][d] = DoFTools::none;
 * 
 *       DoFTools::make_sparsity_pattern(dof_handler,
 *                                       preconditioner_coupling,
 *                                       preconditioner_dsp,
 *                                       constraints,
 *                                       false);
 * 
 *       preconditioner_sparsity_pattern.copy_from(preconditioner_dsp);
 *     }
 * 
 * @endcode
 * 
 * Finally, the system matrix, the preconsitioner matrix, the solution and
 * the right hand side vector are created from the block structure similar
 * to the approach in @ref step_20 "step-20":
 * 
 * @code
 *     system_matrix.reinit(sparsity_pattern);
 *     preconditioner_matrix.reinit(preconditioner_sparsity_pattern);
 * 
 *     solution.reinit(2);
 *     solution.block(0).reinit(n_u);
 *     solution.block(1).reinit(n_p);
 *     solution.collect_sizes();
 * 
 *     system_rhs.reinit(2);
 *     system_rhs.block(0).reinit(n_u);
 *     system_rhs.block(1).reinit(n_p);
 *     system_rhs.collect_sizes();
 *   }
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="StokesProblemassemble_system"></a> 
 * <h4>StokesProblem::assemble_system</h4>
 * 

 * 
 * The assembly process follows the discussion in @ref step_20 "step-20" and in the
 * introduction. We use the well-known abbreviations for the data structures
 * that hold the local matrices, right hand side, and global numbering of the
 * degrees of freedom for the present cell.
 * 
 * @code
 *   template <int dim>
 *   void StokesProblem<dim>::assemble_system()
 *   {
 *     system_matrix         = 0;
 *     system_rhs            = 0;
 *     preconditioner_matrix = 0;
 * 
 *     QGauss<dim> quadrature_formula(degree + 2);
 * 
 *     FEValues<dim> fe_values(fe,
 *                             quadrature_formula,
 *                             update_values | update_quadrature_points |
 *                               update_JxW_values | update_gradients);
 * 
 *     const unsigned int dofs_per_cell = fe.dofs_per_cell;
 * 
 *     const unsigned int n_q_points = quadrature_formula.size();
 * 
 *     FullMatrix<double> local_matrix(dofs_per_cell, dofs_per_cell);
 *     FullMatrix<double> local_preconditioner_matrix(dofs_per_cell,
 *                                                    dofs_per_cell);
 *     Vector<double>     local_rhs(dofs_per_cell);
 * 
 *     std::vector<types::global_dof_index> local_dof_indices(dofs_per_cell);
 * 
 *     const RightHandSide<dim>    right_hand_side;
 *     std::vector<Vector<double>> rhs_values(n_q_points, Vector<double>(dim + 1));
 * 
 * @endcode
 * 
 * Next, we need two objects that work as extractors for the FEValues
 * object. Their use is explained in detail in the report on @ref
 * vector_valued :
 * 
 * @code
 *     const FEValuesExtractors::Vector velocities(0);
 *     const FEValuesExtractors::Scalar pressure(dim);
 * 
 * @endcode
 * 
 * As an extension over @ref step_20 "step-20" and @ref step_21 "step-21", we include a few optimizations
 * that make assembly much faster for this particular problem. The
 * improvements are based on the observation that we do a few calculations
 * too many times when we do as in @ref step_20 "step-20": The symmetric gradient actually
 * has <code>dofs_per_cell</code> different values per quadrature point, but
 * we extract it <code>dofs_per_cell*dofs_per_cell</code> times from the
 * FEValues object - for both the loop over <code>i</code> and the inner
 * loop over <code>j</code>. In 3d, that means evaluating it @f$89^2=7921@f$
 * instead of @f$89@f$ times, a not insignificant difference.
 *     

 * 
 * So what we're going to do here is to avoid such repeated calculations
 * by getting a vector of rank-2 tensors (and similarly for the divergence
 * and the basis function value on pressure) at the quadrature point prior
 * to starting the loop over the dofs on the cell. First, we create the
 * respective objects that will hold these values. Then, we start the loop
 * over all cells and the loop over the quadrature points, where we first
 * extract these values. There is one more optimization we implement here:
 * the local matrix (as well as the global one) is going to be symmetric,
 * since all the operations involved are symmetric with respect to @f$i@f$ and
 * @f$j@f$. This is implemented by simply running the inner loop not to
 * <code>dofs_per_cell</code>, but only up to <code>i</code>, the index of
 * the outer loop.
 * 
 * @code
 *     std::vector<SymmetricTensor<2, dim>> symgrad_phi_u(dofs_per_cell);
 *     std::vector<double>                  div_phi_u(dofs_per_cell);
 *     std::vector<double>                  phi_p(dofs_per_cell);
 * 
 *     for (const auto &cell : dof_handler.active_cell_iterators())
 *       {
 *         fe_values.reinit(cell);
 *         local_matrix                = 0;
 *         local_preconditioner_matrix = 0;
 *         local_rhs                   = 0;
 * 
 *         right_hand_side.vector_value_list(fe_values.get_quadrature_points(),
 *                                           rhs_values);
 * 
 *         for (unsigned int q = 0; q < n_q_points; ++q)
 *           {
 *             for (unsigned int k = 0; k < dofs_per_cell; ++k)
 *               {
 *                 symgrad_phi_u[k] =
 *                   fe_values[velocities].symmetric_gradient(k, q);
 *                 div_phi_u[k] = fe_values[velocities].divergence(k, q);
 *                 phi_p[k]     = fe_values[pressure].value(k, q);
 *               }
 * 
 * @endcode
 * 
 * Now finally for the bilinear forms of both the system matrix and
 * the matrix we use for the preconditioner. Recall that the
 * formulas for these two are
 * @f{align*}{
 * A_{ij} &= a(\varphi_i,\varphi_j)
 * \\     &= \underbrace{2(\varepsilon(\varphi_{i,\textbf{u}}),
 * \varepsilon(\varphi_{j,\textbf{u}}))_{\Omega}}
 * _{(1)}
 * \;
 * \underbrace{- (\textrm{div}\; \varphi_{i,\textbf{u}},
 * \varphi_{j,p})_{\Omega}}
 * _{(2)}
 * \;
 * \underbrace{- (\varphi_{i,p},
 * \textrm{div}\;
 * \varphi_{j,\textbf{u}})_{\Omega}}
 * _{(3)}
 * @f}
 * and
 * @f{align*}{
 * M_{ij} &= \underbrace{(\varphi_{i,p},
 * \varphi_{j,p})_{\Omega}}
 * _{(4)},
 * @f}
 * respectively, where @f$\varphi_{i,\textbf{u}}@f$ and @f$\varphi_{i,p}@f$
 * are the velocity and pressure components of the @f$i@f$th shape
 * function. The various terms above are then easily recognized in
 * the following implementation:
 * 
 * @code
 *             for (unsigned int i = 0; i < dofs_per_cell; ++i)
 *               {
 *                 for (unsigned int j = 0; j <= i; ++j)
 *                   {
 *                     local_matrix(i, j) +=
 *                       (2 * (symgrad_phi_u[i] * symgrad_phi_u[j]) // (1)
 *                        - div_phi_u[i] * phi_p[j]                 // (2)
 *                        - phi_p[i] * div_phi_u[j])                // (3)
 *                       * fe_values.JxW(q);                        // * dx
 * 
 *                     local_preconditioner_matrix(i, j) +=
 *                       (phi_p[i] * phi_p[j]) // (4)
 *                       * fe_values.JxW(q);   // * dx
 *                   }
 * @endcode
 * 
 * Note that in the implementation of (1) above, `operator*`
 * is overloaded for symmetric tensors, yielding the scalar
 * product between the two tensors.
 *                 

 * 
 * For the right-hand side we use the fact that the shape
 * functions are only non-zero in one component (because our
 * elements are primitive).  Instead of multiplying the tensor
 * representing the dim+1 values of shape function i with the
 * whole right-hand side vector, we only look at the only
 * non-zero component. The function
 * FiniteElement::system_to_component_index will return
 * which component this shape function lives in (0=x velocity,
 * 1=y velocity, 2=pressure in 2d), which we use to pick out
 * the correct component of the right-hand side vector to
 * multiply with.
 * 
 * @code
 *                 const unsigned int component_i =
 *                   fe.system_to_component_index(i).first;
 *                 local_rhs(i) += (fe_values.shape_value(i, q)   // (phi_u_i(x_q)
 *                                  * rhs_values[q](component_i)) // * f(x_q))
 *                                 * fe_values.JxW(q);            // * dx
 *               }
 *           }
 * 
 * @endcode
 * 
 * Before we can write the local data into the global matrix (and
 * simultaneously use the AffineConstraints object to apply
 * Dirichlet boundary conditions and eliminate hanging node constraints,
 * as we discussed in the introduction), we have to be careful about one
 * thing, though. We have only built half of the local matrices
 * because of symmetry, but we're going to save the full matrices
 * in order to use the standard functions for solving. This is done
 * by flipping the indices in case we are pointing into the empty part
 * of the local matrices.
 * 
 * @code
 *         for (unsigned int i = 0; i < dofs_per_cell; ++i)
 *           for (unsigned int j = i + 1; j < dofs_per_cell; ++j)
 *             {
 *               local_matrix(i, j) = local_matrix(j, i);
 *               local_preconditioner_matrix(i, j) =
 *                 local_preconditioner_matrix(j, i);
 *             }
 * 
 *         cell->get_dof_indices(local_dof_indices);
 *         constraints.distribute_local_to_global(local_matrix,
 *                                                local_rhs,
 *                                                local_dof_indices,
 *                                                system_matrix,
 *                                                system_rhs);
 *         constraints.distribute_local_to_global(local_preconditioner_matrix,
 *                                                local_dof_indices,
 *                                                preconditioner_matrix);
 *       }
 * 
 * @endcode
 * 
 * Before we're going to solve this linear system, we generate a
 * preconditioner for the velocity-velocity matrix, i.e.,
 * <code>block(0,0)</code> in the system matrix. As mentioned above, this
 * depends on the spatial dimension. Since the two classes described by
 * the <code>InnerPreconditioner::type</code> alias have the same
 * interface, we do not have to do anything different whether we want to
 * use a sparse direct solver or an ILU:
 * 
 * @code
 *     std::cout << "   Computing preconditioner..." << std::endl << std::flush;
 * 
 *     A_preconditioner =
 *       std::make_shared<typename InnerPreconditioner<dim>::type>();
 *     A_preconditioner->initialize(
 *       system_matrix.block(0, 0),
 *       typename InnerPreconditioner<dim>::type::AdditionalData());
 *   }
 * 
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="StokesProblemsolve"></a> 
 * <h4>StokesProblem::solve</h4>
 * 

 * 
 * After the discussion in the introduction and the definition of the
 * respective classes above, the implementation of the <code>solve</code>
 * function is rather straight-forward and done in a similar way as in
 * @ref step_20 "step-20". To start with, we need an object of the
 * <code>InverseMatrix</code> class that represents the inverse of the
 * matrix A. As described in the introduction, the inverse is generated with
 * the help of an inner preconditioner of type
 * <code>InnerPreconditioner::type</code>.
 * 
 * @code
 *   template <int dim>
 *   void StokesProblem<dim>::solve()
 *   {
 *     const InverseMatrix<SparseMatrix<double>,
 *                         typename InnerPreconditioner<dim>::type>
 *                    A_inverse(system_matrix.block(0, 0), *A_preconditioner);
 *     Vector<double> tmp(solution.block(0).size());
 * 
 * @endcode
 * 
 * This is as in @ref step_20 "step-20". We generate the right hand side @f$B A^{-1} F - G@f$
 * for the Schur complement and an object that represents the respective
 * linear operation @f$B A^{-1} B^T@f$, now with a template parameter
 * indicating the preconditioner - in accordance with the definition of
 * the class.
 * 
 * @code
 *     {
 *       Vector<double> schur_rhs(solution.block(1).size());
 *       A_inverse.vmult(tmp, system_rhs.block(0));
 *       system_matrix.block(1, 0).vmult(schur_rhs, tmp);
 *       schur_rhs -= system_rhs.block(1);
 * 
 *       SchurComplement<typename InnerPreconditioner<dim>::type> schur_complement(
 *         system_matrix, A_inverse);
 * 
 * @endcode
 * 
 * The usual control structures for the solver call are created...
 * 
 * @code
 *       SolverControl            solver_control(solution.block(1).size(),
 *                                    1e-6 * schur_rhs.l2_norm());
 *       SolverCG<Vector<double>> cg(solver_control);
 * 
 * @endcode
 * 
 * Now to the preconditioner to the Schur complement. As explained in
 * the introduction, the preconditioning is done by a mass matrix in the
 * pressure variable.
 *       

 * 
 * Actually, the solver needs to have the preconditioner in the form
 * @f$P^{-1}@f$, so we need to create an inverse operation. Once again, we
 * use an object of the class <code>InverseMatrix</code>, which
 * implements the <code>vmult</code> operation that is needed by the
 * solver.  In this case, we have to invert the pressure mass matrix. As
 * it already turned out in earlier tutorial programs, the inversion of
 * a mass matrix is a rather cheap and straight-forward operation
 * (compared to, e.g., a Laplace matrix). The CG method with ILU
 * preconditioning converges in 5-10 steps, independently on the mesh
 * size.  This is precisely what we do here: We choose another ILU
 * preconditioner and take it along to the InverseMatrix object via the
 * corresponding template parameter.  A CG solver is then called within
 * the vmult operation of the inverse matrix.
 *       

 * 
 * An alternative that is cheaper to build, but needs more iterations
 * afterwards, would be to choose a SSOR preconditioner with factor
 * 1.2. It needs about twice the number of iterations, but the costs for
 * its generation are almost negligible.
 * 
 * @code
 *       SparseILU<double> preconditioner;
 *       preconditioner.initialize(preconditioner_matrix.block(1, 1),
 *                                 SparseILU<double>::AdditionalData());
 * 
 *       InverseMatrix<SparseMatrix<double>, SparseILU<double>> m_inverse(
 *         preconditioner_matrix.block(1, 1), preconditioner);
 * 
 * @endcode
 * 
 * With the Schur complement and an efficient preconditioner at hand, we
 * can solve the respective equation for the pressure (i.e. block 0 in
 * the solution vector) in the usual way:
 * 
 * @code
 *       cg.solve(schur_complement, solution.block(1), schur_rhs, m_inverse);
 * 
 * @endcode
 * 
 * After this first solution step, the hanging node constraints have to
 * be distributed to the solution in order to achieve a consistent
 * pressure field.
 * 
 * @code
 *       constraints.distribute(solution);
 * 
 *       std::cout << "  " << solver_control.last_step()
 *                 << " outer CG Schur complement iterations for pressure"
 *                 << std::endl;
 *     }
 * 
 * @endcode
 * 
 * As in @ref step_20 "step-20", we finally need to solve for the velocity equation where
 * we plug in the solution to the pressure equation. This involves only
 * objects we already know - so we simply multiply @f$p@f$ by @f$B^T@f$, subtract
 * the right hand side and multiply by the inverse of @f$A@f$. At the end, we
 * need to distribute the constraints from hanging nodes in order to
 * obtain a consistent flow field:
 * 
 * @code
 *     {
 *       system_matrix.block(0, 1).vmult(tmp, solution.block(1));
 *       tmp *= -1;
 *       tmp += system_rhs.block(0);
 * 
 *       A_inverse.vmult(solution.block(0), tmp);
 * 
 *       constraints.distribute(solution);
 *     }
 *   }
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="StokesProblemoutput_results"></a> 
 * <h4>StokesProblem::output_results</h4>
 * 

 * 
 * The next function generates graphical output. In this example, we are
 * going to use the VTK file format.  We attach names to the individual
 * variables in the problem: <code>velocity</code> to the <code>dim</code>
 * components of velocity and <code>pressure</code> to the pressure.
 *   

 * 
 * Not all visualization programs have the ability to group individual
 * vector components into a vector to provide vector plots; in particular,
 * this holds for some VTK-based visualization programs. In this case, the
 * logical grouping of components into vectors should already be described
 * in the file containing the data. In other words, what we need to do is
 * provide our output writers with a way to know which of the components of
 * the finite element logically form a vector (with @f$d@f$ components in @f$d@f$
 * space dimensions) rather than letting them assume that we simply have a
 * bunch of scalar fields.  This is achieved using the members of the
 * <code>DataComponentInterpretation</code> namespace: as with the filename,
 * we create a vector in which the first <code>dim</code> components refer
 * to the velocities and are given the tag
 * DataComponentInterpretation::component_is_part_of_vector; we
 * finally push one tag
 * DataComponentInterpretation::component_is_scalar to describe
 * the grouping of the pressure variable.
 * 

 * 
 * The rest of the function is then the same as in @ref step_20 "step-20".
 * 
 * @code
 *   template <int dim>
 *   void
 *   StokesProblem<dim>::output_results(const unsigned int refinement_cycle) const
 *   {
 *     std::vector<std::string> solution_names(dim, "velocity");
 *     solution_names.emplace_back("pressure");
 * 
 *     std::vector<DataComponentInterpretation::DataComponentInterpretation>
 *       data_component_interpretation(
 *         dim, DataComponentInterpretation::component_is_part_of_vector);
 *     data_component_interpretation.push_back(
 *       DataComponentInterpretation::component_is_scalar);
 * 
 *     DataOut<dim> data_out;
 *     data_out.attach_dof_handler(dof_handler);
 *     data_out.add_data_vector(solution,
 *                              solution_names,
 *                              DataOut<dim>::type_dof_data,
 *                              data_component_interpretation);
 *     data_out.build_patches();
 * 
 *     std::ofstream output(
 *       "solution-" + Utilities::int_to_string(refinement_cycle, 2) + ".vtk");
 *     data_out.write_vtk(output);
 *   }
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="StokesProblemrefine_mesh"></a> 
 * <h4>StokesProblem::refine_mesh</h4>
 * 

 * 
 * This is the last interesting function of the <code>StokesProblem</code>
 * class.  As indicated by its name, it takes the solution to the problem
 * and refines the mesh where this is needed. The procedure is the same as
 * in the respective step in @ref step_6 "step-6", with the exception that we base the
 * refinement only on the change in pressure, i.e., we call the Kelly error
 * estimator with a mask object of type ComponentMask that selects the
 * single scalar component for the pressure that we are interested in (we
 * get such a mask from the finite element class by specifying the component
 * we want). Additionally, we do not coarsen the grid again:
 * 
 * @code
 *   template <int dim>
 *   void StokesProblem<dim>::refine_mesh()
 *   {
 *     Vector<float> estimated_error_per_cell(triangulation.n_active_cells());
 * 
 *     FEValuesExtractors::Scalar pressure(dim);
 *     KellyErrorEstimator<dim>::estimate(
 *       dof_handler,
 *       QGauss<dim - 1>(degree + 1),
 *       std::map<types::boundary_id, const Function<dim> *>(),
 *       solution,
 *       estimated_error_per_cell,
 *       fe.component_mask(pressure));
 * 
 *     GridRefinement::refine_and_coarsen_fixed_number(triangulation,
 *                                                     estimated_error_per_cell,
 *                                                     0.3,
 *                                                     0.0);
 *     triangulation.execute_coarsening_and_refinement();
 *   }
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="StokesProblemrun"></a> 
 * <h4>StokesProblem::run</h4>
 * 

 * 
 * The last step in the Stokes class is, as usual, the function that
 * generates the initial grid and calls the other functions in the
 * respective order.
 *   

 * 
 * We start off with a rectangle of size @f$4 \times 1@f$ (in 2d) or @f$4 \times 1
 * \times 1@f$ (in 3d), placed in @f$R^2/R^3@f$ as @f$(-2,2)\times(-1,0)@f$ or
 * @f$(-2,2)\times(0,1)\times(-1,0)@f$, respectively. It is natural to start
 * with equal mesh size in each direction, so we subdivide the initial
 * rectangle four times in the first coordinate direction. To limit the
 * scope of the variables involved in the creation of the mesh to the range
 * where we actually need them, we put the entire block between a pair of
 * braces:
 * 
 * @code
 *   template <int dim>
 *   void StokesProblem<dim>::run()
 *   {
 *     {
 *       std::vector<unsigned int> subdivisions(dim, 1);
 *       subdivisions[0] = 4;
 * 
 *       const Point<dim> bottom_left = (dim == 2 ?                
 *                                         Point<dim>(-2, -1) :    // 2d case
 *                                         Point<dim>(-2, 0, -1)); // 3d case
 * 
 *       const Point<dim> top_right = (dim == 2 ?              
 *                                       Point<dim>(2, 0) :    // 2d case
 *                                       Point<dim>(2, 1, 0)); // 3d case
 * 
 *       GridGenerator::subdivided_hyper_rectangle(triangulation,
 *                                                 subdivisions,
 *                                                 bottom_left,
 *                                                 top_right);
 *     }
 * 
 * @endcode
 * 
 * A boundary indicator of 1 is set to all boundaries that are subject to
 * Dirichlet boundary conditions, i.e.  to faces that are located at 0 in
 * the last coordinate direction. See the example description above for
 * details.
 * 
 * @code
 *     for (const auto &cell : triangulation.active_cell_iterators())
 *       for (const auto &face : cell->face_iterators())
 *         if (face->center()[dim - 1] == 0)
 *           face->set_all_boundary_ids(1);
 * 
 * 
 * @endcode
 * 
 * We then apply an initial refinement before solving for the first
 * time. In 3D, there are going to be more degrees of freedom, so we
 * refine less there:
 * 
 * @code
 *     triangulation.refine_global(4 - dim);
 * 
 * @endcode
 * 
 * As first seen in @ref step_6 "step-6", we cycle over the different refinement levels
 * and refine (except for the first cycle), setup the degrees of freedom
 * and matrices, assemble, solve and create output:
 * 
 * @code
 *     for (unsigned int refinement_cycle = 0; refinement_cycle < 6;
 *          ++refinement_cycle)
 *       {
 *         std::cout << "Refinement cycle " << refinement_cycle << std::endl;
 * 
 *         if (refinement_cycle > 0)
 *           refine_mesh();
 * 
 *         setup_dofs();
 * 
 *         std::cout << "   Assembling..." << std::endl << std::flush;
 *         assemble_system();
 * 
 *         std::cout << "   Solving..." << std::flush;
 *         solve();
 * 
 *         output_results(refinement_cycle);
 * 
 *         std::cout << std::endl;
 *       }
 *   }
 * } // namespace Step22
 * 
 * 
 * @endcode
 * 
 * 
 * <a name="Thecodemaincodefunction"></a> 
 * <h3>The <code>main</code> function</h3>
 * 

 * 
 * The main function is the same as in @ref step_20 "step-20". We pass the element degree as
 * a parameter and choose the space dimension at the well-known template slot.
 * 
 * @code
 * int main()
 * {
 *   try
 *     {
 *       using namespace Step22;
 * 
 *       StokesProblem<2> flow_problem(1);
 *       flow_problem.run();
 *     }
 *   catch (std::exception &exc)
 *     {
 *       std::cerr << std::endl
 *                 << std::endl
 *                 << "----------------------------------------------------"
 *                 << std::endl;
 *       std::cerr << "Exception on processing: " << std::endl
 *                 << exc.what() << std::endl
 *                 << "Aborting!" << std::endl
 *                 << "----------------------------------------------------"
 *                 << std::endl;
 * 
 *       return 1;
 *     }
 *   catch (...)
 *     {
 *       std::cerr << std::endl
 *                 << std::endl
 *                 << "----------------------------------------------------"
 *                 << std::endl;
 *       std::cerr << "Unknown exception!" << std::endl
 *                 << "Aborting!" << std::endl
 *                 << "----------------------------------------------------"
 *                 << std::endl;
 *       return 1;
 *     }
 * 
 *   return 0;
 * }
 * @endcode
<a name="Results"></a>
<a name="Results"></a><h1>Results</h1>


<a name="Outputoftheprogramandgraphicalvisualization"></a><h3>Output of the program and graphical visualization</h3>


<a name="2Dcalculations"></a><h4>2D calculations</h4>


Running the program with the space dimension set to 2 in the <code>main</code>
function yields the following output (in "release mode",
See also <a href="http://www.math.colostate.edu/~bangerth/videos.676.18.html">video lecture 18</a>.):
@code
examples/step-22> make run
Refinement cycle 0
   Number of active cells: 64
   Number of degrees of freedom: 679 (594+85)
   Assembling...
   Computing preconditioner...
   Solving...  11 outer CG Schur complement iterations for pressure

Refinement cycle 1
   Number of active cells: 160
   Number of degrees of freedom: 1683 (1482+201)
   Assembling...
   Computing preconditioner...
   Solving...  11 outer CG Schur complement iterations for pressure

Refinement cycle 2
   Number of active cells: 376
   Number of degrees of freedom: 3813 (3370+443)
   Assembling...
   Computing preconditioner...
   Solving...  11 outer CG Schur complement iterations for pressure

Refinement cycle 3
   Number of active cells: 880
   Number of degrees of freedom: 8723 (7722+1001)
   Assembling...
   Computing preconditioner...
   Solving...  11 outer CG Schur complement iterations for pressure

Refinement cycle 4
   Number of active cells: 2008
   Number of degrees of freedom: 19383 (17186+2197)
   Assembling...
   Computing preconditioner...
   Solving...  11 outer CG Schur complement iterations for pressure

Refinement cycle 5
   Number of active cells: 4288
   Number of degrees of freedom: 40855 (36250+4605)
   Assembling...
   Computing preconditioner...
   Solving...  11 outer CG Schur complement iterations for pressure
@endcode

The entire computation above takes about 2 seconds on a reasonably
quick (for 2015 standards) machine.

What we see immediately from this is that the number of (outer)
iterations does not increase as we refine the mesh. This confirms the
statement in the introduction that preconditioning the Schur
complement with the mass matrix indeed yields a matrix spectrally
equivalent to the identity matrix (i.e. with eigenvalues bounded above
and below independently of the mesh size or the relative sizes of
cells). In other words, the mass matrix and the Schur complement are
spectrally equivalent.

In the images below, we show the grids for the first six refinement
steps in the program.  Observe how the grid is refined in regions
where the solution rapidly changes: On the upper boundary, we have
Dirichlet boundary conditions that are -1 in the left half of the line
and 1 in the right one, so there is an abrupt change at @f$x=0@f$. Likewise,
there are changes from Dirichlet to Neumann data in the two upper
corners, so there is need for refinement there as well:

<table width="60%" align="center">
  <tr>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.2d.mesh-0.png" alt="">
    </td>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.2d.mesh-1.png" alt="">
    </td>
  </tr>
  <tr>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.2d.mesh-2.png" alt="">
    </td>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.2d.mesh-3.png" alt="">
    </td>
  </tr>
  <tr>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.2d.mesh-4.png" alt="">
    </td>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.2d.mesh-5.png" alt="">
    </td>
  </tr>
</table>

Finally, following is a plot of the flow field. It shows fluid
transported along with the moving upper boundary and being replaced by
material coming from below:

<img src="https://www.dealii.org/images/steps/developer/step-22.2d.solution.png" alt="">

This plot uses the capability of VTK-based visualization programs (in
this case of VisIt) to show vector data; this is the result of us
declaring the velocity components of the finite element in use to be a
set of vector components, rather than independent scalar components in
the <code>StokesProblem@<dim@>::%output_results</code> function of this
tutorial program.



<a name="3Dcalculations"></a><h4>3D calculations</h4>


In 3d, the screen output of the program looks like this:

@code
Refinement cycle 0
   Number of active cells: 32
   Number of degrees of freedom: 1356 (1275+81)
   Assembling...
   Computing preconditioner...
   Solving...  13 outer CG Schur complement iterations for pressure.

Refinement cycle 1
   Number of active cells: 144
   Number of degrees of freedom: 5088 (4827+261)
   Assembling...
   Computing preconditioner...
   Solving...  14 outer CG Schur complement iterations for pressure.

Refinement cycle 2
   Number of active cells: 704
   Number of degrees of freedom: 22406 (21351+1055)
   Assembling...
   Computing preconditioner...
   Solving...  14 outer CG Schur complement iterations for pressure.

Refinement cycle 3
   Number of active cells: 3168
   Number of degrees of freedom: 93176 (89043+4133)
   Assembling...
   Computing preconditioner...
   Solving...  15 outer CG Schur complement iterations for pressure.

Refinement cycle 4
   Number of active cells: 11456
   Number of degrees of freedom: 327808 (313659+14149)
   Assembling...
   Computing preconditioner...
   Solving...  15 outer CG Schur complement iterations for pressure.

Refinement cycle 5
   Number of active cells: 45056
   Number of degrees of freedom: 1254464 (1201371+53093)
   Assembling...
   Computing preconditioner...
   Solving...  14 outer CG Schur complement iterations for pressure.
@endcode

Again, we see that the number of outer iterations does not increase as
we refine the mesh. Nevertheless, the compute time increases
significantly: for each of the iterations above separately, it takes about
0.14 seconds, 0.63 seconds, 4.8 seconds, 35 seconds, 2 minutes and 33 seconds,
and 13 minutes and 12 seconds. This overall superlinear (in the number of
unknowns) increase in runtime is due to the fact that our inner solver is not
@f${\cal O}(N)@f$: a simple experiment shows that as we keep refining the mesh, the
average number of ILU-preconditioned CG iterations to invert the
velocity-velocity block @f$A@f$ increases.

We will address the question of how possibly to improve our solver <a
href="#improved-solver">below</a>.

As for the graphical output, the grids generated during the solution
look as follow:

<table width="60%" align="center">
  <tr>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.3d.mesh-0.png" alt="">
    </td>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.3d.mesh-1.png" alt="">
    </td>
  </tr>
  <tr>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.3d.mesh-2.png" alt="">
    </td>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.3d.mesh-3.png" alt="">
    </td>
  </tr>
  <tr>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.3d.mesh-4.png" alt="">
    </td>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.3d.mesh-5.png" alt="">
    </td>
  </tr>
</table>

Again, they show essentially the location of singularities introduced
by boundary conditions. The vector field computed makes for an
interesting graph:

<img src="https://www.dealii.org/images/steps/developer/step-22.3d.solution.png" alt="">

The isocontours shown here as well are those of the pressure
variable, showing the singularity at the point of discontinuous
velocity boundary conditions.



<a name="Sparsitypattern"></a><h3>Sparsity pattern</h3>


As explained during the generation of the sparsity pattern, it is
important to have the numbering of degrees of freedom in mind when
using preconditioners like incomplete LU decompositions. This is most
conveniently visualized using the distribution of nonzero elements in
the stiffness matrix.

If we don't do anything special to renumber degrees of freedom (i.e.,
without using DoFRenumbering::Cuthill_McKee, but with using
DoFRenumbering::component_wise to ensure that degrees of freedom are
appropriately sorted into their corresponding blocks of the matrix and
vector), then we get the following image after the first adaptive
refinement in two dimensions:

<img src="https://www.dealii.org/images/steps/developer/step-22.2d.sparsity-nor.png" alt="">

In order to generate such a graph, you have to insert a piece of
code like the following to the end of the setup step.
@code
  {
    std::ofstream out ("sparsity_pattern.gpl");
    sparsity_pattern.print_gnuplot(out);
  }
@endcode

It is clearly visible that the nonzero entries are spread over almost the
whole matrix.  This makes preconditioning by ILU inefficient: ILU generates a
Gaussian elimination (LU decomposition) without fill-in elements, which means
that more tentative fill-ins left out will result in a worse approximation of
the complete decomposition.

In this program, we have thus chosen a more advanced renumbering of
components.  The renumbering with DoFRenumbering::Cuthill_McKee and grouping
the components into velocity and pressure yields the following output:

<img src="https://www.dealii.org/images/steps/developer/step-22.2d.sparsity-ren.png" alt="">

It is apparent that the situation has improved a lot. Most of the elements are
now concentrated around the diagonal in the (0,0) block in the matrix. Similar
effects are also visible for the other blocks. In this case, the ILU
decomposition will be much closer to the full LU decomposition, which improves
the quality of the preconditioner. (It may be interesting to note that the
sparse direct solver UMFPACK does some %internal renumbering of the equations
before actually generating a sparse LU decomposition; that procedure leads to
a very similar pattern to the one we got from the Cuthill-McKee algorithm.)

Finally, we want to have a closer
look at a sparsity pattern in 3D. We show only the (0,0) block of the
matrix, again after one adaptive refinement. Apart from the fact that the matrix
size has increased, it is also visible that there are many more entries
in the matrix. Moreover, even for the optimized renumbering, there will be a
considerable amount of tentative fill-in elements. This illustrates why UMFPACK
is not a good choice in 3D - a full decomposition needs many new entries that
 eventually won't fit into the physical memory (RAM):

<img src="https://www.dealii.org/images/steps/developer/step-22.3d.sparsity_uu-ren.png" alt="">



<a name="PossibleExtensions"></a><h3>Possible Extensions</h3>


<a name="improved-solver">
<a name="Improvedlinearsolverin3D"></a><h4>Improved linear solver in 3D</h4>

</a>

We have seen in the section of computational results that the number of outer
iterations does not depend on the mesh size, which is optimal in a sense of
scalability. This does, however, not apply to the solver as a whole, as
mentioned above:
We did not look at the number of inner iterations when generating the inverse of
the matrix @f$A@f$ and the mass matrix @f$M_p@f$. Of course, this is unproblematic in
the 2D case where we precondition @f$A@f$ with a direct solver and the
<code>vmult</code> operation of the inverse matrix structure will converge in
one single CG step, but this changes in 3D where we only use an ILU
preconditioner.  There, the number of required preconditioned CG steps to
invert @f$A@f$ increases as the mesh is refined, and each <code>vmult</code>
operation involves on average approximately 14, 23, 36, 59, 75 and 101 inner
CG iterations in the refinement steps shown above. (On the other hand,
the number of iterations for applying the inverse pressure mass matrix is
always around five, both in two and three dimensions.)  To summarize, most work
is spent on solving linear systems with the same matrix @f$A@f$ over and over again.
What makes this look even worse is the fact that we
actually invert a matrix that is about 95 percent the size of the total system
matrix and stands for 85 percent of the non-zero entries in the sparsity
pattern. Hence, the natural question is whether it is reasonable to solve a
linear system with matrix @f$A@f$ for about 15 times when calculating the solution
to the block system.

The answer is, of course, that we can do that in a few other (most of the time
better) ways.
Nevertheless, it has to be remarked that an indefinite system as the one
at hand puts indeed much higher
demands on the linear algebra than standard elliptic problems as we have seen
in the early tutorial programs. The improvements are still rather
unsatisfactory, if one compares with an elliptic problem of similar
size. Either way, we will introduce below a number of improvements to the
linear solver, a discussion that we will re-consider again with additional
options in the @ref step_31 "step-31" program.

<a name="improved-ilu">
<a name="BetterILUdecompositionbysmartreordering"></a><h5>Better ILU decomposition by smart reordering</h5>

</a>
A first attempt to improve the speed of the linear solution process is to choose
a dof reordering that makes the ILU being closer to a full LU decomposition, as
already mentioned in the in-code comments. The DoFRenumbering namespace compares
several choices for the renumbering of dofs for the Stokes equations. The best
result regarding the computing time was found for the King ordering, which is
accessed through the call DoFRenumbering::boost::king_ordering. With that
program, the inner solver needs considerably less operations, e.g. about 62
inner CG iterations for the inversion of @f$A@f$ at cycle 4 compared to about 75
iterations with the standard Cuthill-McKee-algorithm. Also, the computing time
at cycle 4 decreased from about 17 to 11 minutes for the <code>solve()</code>
call. However, the King ordering (and the orderings provided by the
DoFRenumbering::boost namespace in general) has a serious drawback - it uses
much more memory than the in-build deal versions, since it acts on abstract
graphs rather than the geometry provided by the triangulation. In the present
case, the renumbering takes about 5 times as much memory, which yields an
infeasible algorithm for the last cycle in 3D with 1.2 million
unknowns.

<a name="BetterpreconditionerfortheinnerCGsolver"></a><h5>Better preconditioner for the inner CG solver</h5>

Another idea to improve the situation even more would be to choose a
preconditioner that makes CG for the (0,0) matrix @f$A@f$ converge in a
mesh-independent number of iterations, say 10 to 30. We have seen such a
candidate in @ref step_16 "step-16": multigrid.

<a name="BlockSchurcomplementpreconditioner"></a><h5>Block Schur complement preconditioner</h5>

Even with a good preconditioner for @f$A@f$, we still
need to solve of the same linear system repeatedly (with different
right hand sides, though) in order to make the Schur complement solve
converge. The approach we are going to discuss here is how inner iteration
and outer iteration can be combined. If we persist in calculating the Schur
complement, there is no other possibility.

The alternative is to attack the block system at once and use an approximate
Schur complement as efficient preconditioner. The idea is as
follows: If we find a block preconditioner @f$P@f$ such that the matrix
@f{eqnarray*}
  P^{-1}\left(\begin{array}{cc}
    A & B^T \\ B & 0
  \end{array}\right)
@f}
is simple, then an iterative solver with that preconditioner will converge in a
few iterations. Using the Schur complement @f$S = B A^{-1} B^T@f$, one finds that
@f{eqnarray*}
  P^{-1}
  =
  \left(\begin{array}{cc}
    A^{-1} & 0 \\ S^{-1} B A^{-1} & -S^{-1}
  \end{array}\right)
@f}
would appear to be a good choice since
@f{eqnarray*}
  P^{-1}\left(\begin{array}{cc}
    A & B^T \\ B & 0
  \end{array}\right)
  =
  \left(\begin{array}{cc}
    A^{-1} & 0 \\ S^{-1} B A^{-1} & -S^{-1}
  \end{array}\right)\cdot \left(\begin{array}{cc}
    A & B^T \\ B & 0
  \end{array}\right)
  =
  \left(\begin{array}{cc}
    I & A^{-1} B^T \\ 0 & I
  \end{array}\right).
@f}
This is the approach taken by the paper by Silvester and Wathen referenced
to in the introduction (with the exception that Silvester and Wathen use
right preconditioning). In this case, a Krylov-based iterative method would
converge in one step only if exact inverses of @f$A@f$ and @f$S@f$ were applied,
since all the eigenvalues are one (and the number of iterations in such a
method is bounded by the number of distinct eigenvalues). Below, we will
discuss the choice of an adequate solver for this problem. First, we are
going to have a closer look at the implementation of the preconditioner.

Since @f$P@f$ is aimed to be a preconditioner only, we shall use approximations to
the inverse of the Schur complement @f$S@f$ and the matrix @f$A@f$. Hence, the Schur
complement will be approximated by the pressure mass matrix @f$M_p@f$, and we use
a preconditioner to @f$A@f$ (without an InverseMatrix class around it) for
approximating @f$A^{-1}@f$.

Here comes the class that implements the block Schur
complement preconditioner. The <code>vmult</code> operation for block vectors
according to the derivation above can be specified by three successive
operations:
@code
template <class PreconditionerA, class PreconditionerMp>
class BlockSchurPreconditioner : public Subscriptor
{
  public:
    BlockSchurPreconditioner (const BlockSparseMatrix<double>         &S,
          const InverseMatrix<SparseMatrix<double>,PreconditionerMp>  &Mpinv,
          const PreconditionerA &Apreconditioner);

  void vmult (BlockVector<double>       &dst,
              const BlockVector<double> &src) const;

  private:
    const SmartPointer<const BlockSparseMatrix<double> > system_matrix;
    const SmartPointer<const InverseMatrix<SparseMatrix<double>,
                       PreconditionerMp > > m_inverse;
    const PreconditionerA &a_preconditioner;

    mutable Vector<double> tmp;

};

template <class PreconditionerA, class PreconditionerMp>
BlockSchurPreconditioner<PreconditionerA, PreconditionerMp>::BlockSchurPreconditioner(
          const BlockSparseMatrix<double>                            &S,
          const InverseMatrix<SparseMatrix<double>,PreconditionerMp> &Mpinv,
          const PreconditionerA &Apreconditioner
          )
                :
                system_matrix           (&S),
                m_inverse               (&Mpinv),
                a_preconditioner        (Apreconditioner),
                tmp                     (S.block(1,1).m())
{}

        // Now the interesting function, the multiplication of
        // the preconditioner with a BlockVector.
template <class PreconditionerA, class PreconditionerMp>
void BlockSchurPreconditioner<PreconditionerA, PreconditionerMp>::vmult (
                                     BlockVector<double>       &dst,
                                     const BlockVector<double> &src) const
{
        // Form u_new = A^{-1} u
  a_preconditioner.vmult (dst.block(0), src.block(0));
        // Form tmp = - B u_new + p
        // (<code>SparseMatrix::residual</code>
        // does precisely this)
  system_matrix->block(1,0).residual(tmp, dst.block(0), src.block(1));
        // Change sign in tmp
  tmp *= -1;
        // Multiply by approximate Schur complement
        // (i.e. a pressure mass matrix)
  m_inverse->vmult (dst.block(1), tmp);
}
@endcode

Since we act on the whole block system now, we have to live with one
disadvantage: we need to perform the solver iterations on
the full block system instead of the smaller pressure space.

Now we turn to the question which solver we should use for the block
system. The first observation is that the resulting preconditioned matrix cannot
be solved with CG since it is neither positive definite nor symmetric.

The deal.II libraries implement several solvers that are appropriate for the
problem at hand. One choice is the solver @ref SolverBicgstab "BiCGStab", which
was used for the solution of the unsymmetric advection problem in @ref step_9 "step-9". The
second option, the one we are going to choose, is @ref SolverGMRES "GMRES"
(generalized minimum residual). Both methods have their pros and cons - there
are problems where one of the two candidates clearly outperforms the other, and
vice versa.
<a href="http://en.wikipedia.org/wiki/GMRES#Comparison_with_other_solvers">Wikipedia</a>'s
article on the GMRES method gives a comparative presentation.
A more comprehensive and well-founded comparison can be read e.g. in the book by
J.W. Demmel (Applied Numerical Linear Algebra, SIAM, 1997, section 6.6.6).

For our specific problem with the ILU preconditioner for @f$A@f$, we certainly need
to perform hundreds of iterations on the block system for large problem sizes
(we won't beat CG!). Actually, this disfavors GMRES: During the GMRES
iterations, a basis of Krylov vectors is successively built up and some
operations are performed on these vectors. The more vectors are in this basis,
the more operations and memory will be needed. The number of operations scales
as @f${\cal O}(n + k^2)@f$ and memory as @f${\cal O}(kn)@f$, where @f$k@f$ is the number of
vectors in the Krylov basis and @f$n@f$ the size of the (block) matrix.
To not let these demands grow excessively, deal.II limits the size @f$k@f$ of the
basis to 30 vectors by default.
Then, the basis is rebuilt. This implementation of the GMRES method is called
GMRES(k), with default @f$k=30@f$. What we have gained by this restriction,
namely a bound on operations and memory requirements, will be compensated by
the fact that we use an incomplete basis - this will increase the number of
required iterations.

BiCGStab, on the other hand, won't get slower when many iterations are needed
(one iteration uses only results from one preceding step and
not all the steps as GMRES). Besides the fact the BiCGStab is more expensive per
step since two matrix-vector products are needed (compared to one for
CG or GMRES), there is one main reason which makes BiCGStab not appropriate for
this problem: The preconditioner applies the inverse of the pressure
mass matrix by using the InverseMatrix class. Since the application of the
inverse matrix to a vector is done only in approximative way (an exact inverse
is too expensive), this will also affect the solver. In the case of BiCGStab,
the Krylov vectors will not be orthogonal due to that perturbation. While
this is uncritical for a small number of steps (up to about 50), it ruins the
performance of the solver when these perturbations have grown to a significant
magnitude in the coarse of iterations.

We did some experiments with BiCGStab and found it to
be faster than GMRES up to refinement cycle 3 (in 3D), but it became very slow
for cycles 4 and 5 (even slower than the original Schur complement), so the
solver is useless in this situation. Choosing a sharper tolerance for the
inverse matrix class (<code>1e-10*src.l2_norm()</code> instead of
<code>1e-6*src.l2_norm()</code>) made BiCGStab perform well also for cycle 4,
but did not change the failure on the very large problems.

GMRES is of course also effected by the approximate inverses, but it is not as
sensitive to orthogonality and retains a relatively good performance also for
large sizes, see the results below.

With this said, we turn to the realization of the solver call with GMRES with
@f$k=100@f$ temporary vectors:

@code
      const SparseMatrix<double> &pressure_mass_matrix
        = preconditioner_matrix.block(1,1);
      SparseILU<double> pmass_preconditioner;
      pmass_preconditioner.initialize (pressure_mass_matrix,
        SparseILU<double>::AdditionalData());

      InverseMatrix<SparseMatrix<double>,SparseILU<double> >
        m_inverse (pressure_mass_matrix, pmass_preconditioner);

      BlockSchurPreconditioner<typename InnerPreconditioner<dim>::type,
                               SparseILU<double> >
        preconditioner (system_matrix, m_inverse, *A_preconditioner);

      SolverControl solver_control (system_matrix.m(),
                                    1e-6*system_rhs.l2_norm());
      GrowingVectorMemory<BlockVector<double> > vector_memory;
      SolverGMRES<BlockVector<double> >::AdditionalData gmres_data;
      gmres_data.max_n_tmp_vectors = 100;

      SolverGMRES<BlockVector<double> > gmres(solver_control, vector_memory,
                                              gmres_data);

      gmres.solve(system_matrix, solution, system_rhs,
                  preconditioner);

      constraints.distribute (solution);

      std::cout << " "
                << solver_control.last_step()
                << " block GMRES iterations";
@endcode

Obviously, one needs to add the include file @ref SolverGMRES
"<lac/solver_gmres.h>" in order to make this run.
We call the solver with a BlockVector template in order to enable
GMRES to operate on block vectors and matrices.
Note also that we need to set the (1,1) block in the system
matrix to zero (we saved the pressure mass matrix there which is not part of the
problem) after we copied the information to another matrix.

Using the Timer class, we collect some statistics that compare the runtime
of the block solver with the one from the problem implementation above.
Besides the solution with the two options we also check if the solutions
of the two variants are close to each other (i.e. this solver gives indeed the
same solution as we had before) and calculate the infinity
norm of the vector difference.

Let's first see the results in 2D:
@code
Refinement cycle 0
   Number of active cells: 64
   Number of degrees of freedom: 679 (594+85) [0.00162792 s]
   Assembling...  [0.00108981 s]
   Computing preconditioner... [0.0025959 s]
   Solving...
      Schur complement: 11 outer CG iterations for p  [0.00479603s ]
      Block Schur preconditioner: 12 GMRES iterations [0.00441718 s]
   l_infinity difference between solution vectors: 5.38258e-07

Refinement cycle 1
   Number of active cells: 160
   Number of degrees of freedom: 1683 (1482+201) [0.00345707 s]
   Assembling...  [0.00237417 s]
   Computing preconditioner... [0.00605702 s]
   Solving...
      Schur complement: 11 outer CG iterations for p  [0.0123992s ]
      Block Schur preconditioner: 12 GMRES iterations [0.011909 s]
   l_infinity difference between solution vectors: 1.74658e-05

Refinement cycle 2
   Number of active cells: 376
   Number of degrees of freedom: 3813 (3370+443) [0.00729299 s]
   Assembling...  [0.00529909 s]
   Computing preconditioner... [0.0167508 s]
   Solving...
      Schur complement: 11 outer CG iterations for p  [0.031672s ]
      Block Schur preconditioner: 12 GMRES iterations [0.029232 s]
   l_infinity difference between solution vectors: 7.81569e-06

Refinement cycle 3
   Number of active cells: 880
   Number of degrees of freedom: 8723 (7722+1001) [0.017709 s]
   Assembling...  [0.0126002 s]
   Computing preconditioner... [0.0435679 s]
   Solving...
      Schur complement: 11 outer CG iterations for p  [0.0971651s ]
      Block Schur preconditioner: 12 GMRES iterations [0.0992041 s]
   l_infinity difference between solution vectors: 1.87249e-05

Refinement cycle 4
   Number of active cells: 2008
   Number of degrees of freedom: 19383 (17186+2197) [0.039988 s]
   Assembling...  [0.028281 s]
   Computing preconditioner... [0.118314 s]
   Solving...
      Schur complement: 11 outer CG iterations for p  [0.252133s ]
      Block Schur preconditioner: 13 GMRES iterations [0.269125 s]
   l_infinity difference between solution vectors: 6.38657e-05

Refinement cycle 5
   Number of active cells: 4288
   Number of degrees of freedom: 40855 (36250+4605) [0.0880702 s]
   Assembling...  [0.0603511 s]
   Computing preconditioner... [0.278339 s]
   Solving...
      Schur complement: 11 outer CG iterations for p  [0.53846s ]
      Block Schur preconditioner: 13 GMRES iterations [0.578667 s]
   l_infinity difference between solution vectors: 0.000173363
@endcode

We see that there is no huge difference in the solution time between the
block Schur complement preconditioner solver and the Schur complement
itself. The reason is simple: we used a direct solve as preconditioner for
@f$A@f$ - so we cannot expect any gain by avoiding the inner iterations. We see
that the number of iterations has slightly increased for GMRES, but all in
all the two choices are fairly similar.

The picture of course changes in 3D:

@code
Refinement cycle 0
   Number of active cells: 32
   Number of degrees of freedom: 1356 (1275+81) [0.00845218 s]
   Assembling...  [0.019372 s]
   Computing preconditioner... [0.00712395 s]
   Solving...
      Schur complement: 13 outer CG iterations for p  [0.0320101s ]
      Block Schur preconditioner: 22 GMRES iterations [0.0048759 s]
   l_infinity difference between solution vectors: 2.15942e-05

Refinement cycle 1
   Number of active cells: 144
   Number of degrees of freedom: 5088 (4827+261) [0.0346942 s]
   Assembling...  [0.0857739 s]
   Computing preconditioner... [0.0465031 s]
   Solving...
      Schur complement: 14 outer CG iterations for p  [0.349258s ]
      Block Schur preconditioner: 35 GMRES iterations [0.048759 s]
   l_infinity difference between solution vectors: 1.77657e-05

Refinement cycle 2
   Number of active cells: 704
   Number of degrees of freedom: 22406 (21351+1055) [0.175669 s]
   Assembling...  [0.437447 s]
   Computing preconditioner... [0.286435 s]
   Solving...
      Schur complement: 14 outer CG iterations for p  [3.65519s ]
      Block Schur preconditioner: 63 GMRES iterations [0.497787 s]
   l_infinity difference between solution vectors: 5.08078e-05

Refinement cycle 3
   Number of active cells: 3168
   Number of degrees of freedom: 93176 (89043+4133) [0.790985 s]
   Assembling...  [1.97598 s]
   Computing preconditioner... [1.4325 s]
   Solving...
      Schur complement: 15 outer CG iterations for p  [29.9666s ]
      Block Schur preconditioner: 128 GMRES iterations [5.02645 s]
   l_infinity difference between solution vectors: 0.000119671

Refinement cycle 4
   Number of active cells: 11456
   Number of degrees of freedom: 327808 (313659+14149) [3.44995 s]
   Assembling...  [7.54772 s]
   Computing preconditioner... [5.46306 s]
   Solving...
      Schur complement: 15 outer CG iterations for p  [139.987s ]
      Block Schur preconditioner: 255 GMRES iterations [38.0946 s]
   l_infinity difference between solution vectors: 0.00020793

Refinement cycle 5
   Number of active cells: 45056
   Number of degrees of freedom: 1254464 (1201371+53093) [19.6795 s]
   Assembling...  [28.6586 s]
   Computing preconditioner... [22.401 s]
   Solving...
      Schur complement: 14 outer CG iterations for p  [796.767s ]
      Block Schur preconditioner: 524 GMRES iterations [355.597 s]
   l_infinity difference between solution vectors: 0.000501219
@endcode

Here, the block preconditioned solver is clearly superior to the Schur
complement, but the advantage gets less for more mesh points. This is
because GMRES(k) scales worse with the problem size than CG, as we discussed
above.  Nonetheless, the improvement by a factor of 3-6 for moderate problem
sizes is quite impressive.


<a name="Combiningtheblockpreconditionerandmultigrid"></a><h5>Combining the block preconditioner and multigrid</h5>

An ultimate linear solver for this problem could be imagined as a
combination of an optimal
preconditioner for @f$A@f$ (e.g. multigrid) and the block preconditioner
described above, which is the approach taken in the @ref step_31 "step-31"
and @ref step_32 "step-32" tutorial programs (where we use an algebraic multigrid
method) and @ref step_56 "step-56" (where we use a geometric multigrid method).


<a name="Noblockmatricesandvectors"></a><h5>No block matrices and vectors</h5>

Another possibility that can be taken into account is to not set up a block
system, but rather solve the system of velocity and pressure all at once. The
options are direct solve with UMFPACK (2D) or GMRES with ILU
preconditioning (3D). It should be straightforward to try that.



<a name="Moreinterestingtestcases"></a><h4>More interesting testcases</h4>


The program can of course also serve as a basis to compute the flow in more
interesting cases. The original motivation to write this program was for it to
be a starting point for some geophysical flow problems, such as the
movement of magma under places where continental plates drift apart (for
example mid-ocean ridges). Of course, in such places, the geometry is more
complicated than the examples shown above, but it is not hard to accommodate
for that.

For example, by using the following modification of the boundary values
function
@code
template <int dim>
double
BoundaryValues<dim>::value (const Point<dim>  &p,
                            const unsigned int component) const
{
  Assert (component < this->n_components,
          ExcIndexRange (component, 0, this->n_components));

  const double x_offset = std::atan(p[1]*4)/3;

  if (component == 0)
    return (p[0] < x_offset ? -1 : (p[0] > x_offset ? 1 : 0));
  return 0;
}
@endcode
and the following way to generate the mesh as the domain
@f$[-2,2]\times[-2,2]\times[-1,0]@f$
@code
    std::vector<unsigned int> subdivisions (dim, 1);
    subdivisions[0] = 4;
    if (dim>2)
      subdivisions[1] = 4;

    const Point<dim> bottom_left = (dim == 2 ?
                                    Point<dim>(-2,-1) :
                                    Point<dim>(-2,-2,-1));
    const Point<dim> top_right   = (dim == 2 ?
                                    Point<dim>(2,0) :
                                    Point<dim>(2,2,0));

    GridGenerator::subdivided_hyper_rectangle (triangulation,
                                               subdivisions,
                                               bottom_left,
                                               top_right);
@endcode
then we get images where the fault line is curved:
<table width="60%" align="center">
  <tr>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.3d-extension.png" alt="">
    </td>
    <td align="center">
      <img src="https://www.dealii.org/images/steps/developer/step-22.3d-grid-extension.png" alt="">
    </td>
  </tr>
</table>

 *
 *
<a name="PlainProg"></a>
<h1> The plain program</h1>
@include "step-22.cc"
*/