From dfd85a64fbf9825d95f8c1337505d2d8185a08c7 Mon Sep 17 00:00:00 2001 From: bangerth Date: Mon, 15 Aug 2011 00:22:00 +0000 Subject: [PATCH] More on sparsity. git-svn-id: https://svn.dealii.org/trunk@24063 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/examples/step-2/doc/intro.dox | 22 ++++++++++++++++++---- 1 file changed, 18 insertions(+), 4 deletions(-) diff --git a/deal.II/examples/step-2/doc/intro.dox b/deal.II/examples/step-2/doc/intro.dox index 5b0b69b33d..6c4b30f394 100644 --- a/deal.II/examples/step-2/doc/intro.dox +++ b/deal.II/examples/step-2/doc/intro.dox @@ -36,9 +36,22 @@ number of nonzero entries per row is five, and therefore independent of the total size of the matrix.) Sparsity is one of the distinguishing feature of the finite element method compared to, say, approximating the solution of a partial differential equation using a Taylor expension and matching -coefficients, or using a Fourier basis. In practical terms, it is the sparsity -of matrices that enables us to solve problems with millions or billions of -unknowns. +coefficients, or using a Fourier basis. + +In practical terms, it is the sparsity of matrices that enables us to solve +problems with millions or billions of unknowns. To understand this, note that +a matrix with $N$ rows, each with a fixed upper bound for the number of +nonzero entries, requires ${\cal O}(N)$ memory locations for storage, and a +matrix-vector multiplication also requires only ${\cal O}(N)$ +operations. Consequently, if we had a linear solver that requires only a fixed +number of matrix-vector multiplications to come up with the solution of a +linear system with this matrix, then we would have a solver that can find the +values of all $N$ unknowns with optimal complexity, i.e., with a total of +${\cal O}(N)$ operations. It is clear that this wouldn't be possible if the +matrix were not sparse, but it also requires very specialized solvers such as +multigrid methods to satisfy the requirement that the solution requires only a +fixed number of matrix-vector multiplications. We will frequently look at the +question of what solver to use in the remaining programs of this tutorial. The sparsity is generated by the fact that finite element shape functions are defined locally on individual cells, rather than @@ -50,5 +63,6 @@ optimized for any particular purpose. However, for some algorithms, especially for some linear solvers and preconditioners, it is advantageous to have the degrees of freedom numbered in a certain order, and we will use the algorithm of Cuthill and McKee to do -so. The results are written to a file and visualized using GNUPLOT; you get to +so. The results are written to a file and visualized using a simple +visualization program; you get to see the outcome in the results section below. -- 2.39.5