D.4 About Zero Columns and Eigenvalues
Lemma D.5 If thei’th column (row) of a matrixAis a zero column (row), then the correspondingi’th row (column) does not influence the eigenvalues of the system.
Proof:Consider a matrix with a zero column
2 nonzero solutions whenA Iis singular. Singularity also implies the determinantjA Ij=0. A standard procedure to find all eigenvalues is to subtractfrom the diagonal, set the determinant to zero and solve for,
Following the rules of linear algebra then
so every row corresponding to a zero column have no effect on any of the eigenvalues. The proof for a zero row follows same procedure.
For reference, consult a linear algebra book, e.g. [Eisi93].
144 Notes
A
P P E N D I XE Elliptic PDE
This section will define and describe the different types of linear sec-ond order PDE’s. It is mainly based on [Stra92]. We will use the nota-tionux=@xu=@u=@x.
Consider a second order PDE of the form
au
xx +bu
xy +cu
yy +du
x +eu
y
+fu+g=0; (E.1)
Consider now an equation substitutingxforuxandx2foruxx, omit-ting lover order terms:
ax 2
+bxy+cy 2
+=0: (E.2)
Depending on a, b, and c, assuming they are not all zero, this will describe either an ellipse, a parabola or a hyperbola. In each of the three cases Equation (E.2) can be reduced by a coordinate transform tox2+y2+ = 0,x2+ = 0, orx2 y2+ =0respectively.
The same can be applied to a second order PDE, transforming the PDE into one of the canonical forms:
b 2
4ac<0: Elliptic, and (E.1) can be transformed to
u
xx +u
yy
+=0; (E.3)
146 Elliptic PDE
b 2
4ac=0: Parabolic, and (E.1) can be transformed to
u
xx
+=0; (E.4)
b 2
4ac>0: Hyperbolic, and (E.1) can be transformed to
u
xx u
yy
+=0; (E.5)
This is the definition in 2D.
Let us consider the second order PDE (E.1) in a linear algebra context.
The PDE using matrix notation can be written as
wherer(u)contain all remaining lower order terms. To Transform the second order PDE into one of its canonical forms corresponds to make an eigenvalue decomposition of the coefficient matrix.
In general, a second order PDE in any dimensionncan be written as Call the matrixA, the following defines the type of the PDE:
The PDE is elliptic, if all eigenvalues ofAhave the same sign.
ThenAis positive (or negative) definite.
The PDE is parabolic if one eigenvalue is zero, and the rest have the same sign.
The PDE is hyperbolic if one eigenvalue have opposite sign of all the others, but none are zero. If there are at least two positive and two negative, the PDE is sometimes called ultra-hyperbolic.
If the coefficient matrixAdepends on the positionx, then a PDE may be elliptic in some regions, parabolic in others, and hyperbolic somewhere else.
Elliptic PDE 147
The different types of PDEs have quite different behavior, which can be described by their characteristic lines. The characteristic lines are said to limit the domain of influence: If the characteristic lines are drawn through a point(x0;y0), then the solution in that point can only influence the solution at other points within the characteristic lines, the gray region in Figure E.1. Often, they-axis is the time axis. Note
c
2Figure E.1:Domain of influence
that the lines may be curves in some cases. The characteristic lines set the speed of propagation of the system.
Returning to the two dimensional case, then the characteristic lines are defined as
@y
If now the PDE is hyperbolic,b2 4ac>0, then two characteristic lines exist, which is exactly the case in Figure E.1.
If however the PDE is parabolic,b2 4ac=0, then there is only on characteristic line. For simplicity, assume that alsob=0 (oth-erwise transform first to one of the canonical forms), then the characteristic line is horizontal. The domain of influence have become the entire half plane above the line, the speed of
propa-148 Elliptic PDE gation has become infinite. Any forcing at(x0;y0)will influence the solution in any point(x;y)fory>y0.
If finally the PDE is elliptic,b2 4ac<0, there are no real char-acteristic lines. Still the speed of propagation is infinite, but now the domain of influence is the entire domain.
E.1 Examples of the Different PDE Types
Hyperbolic. The wave equation is hyperbolic. If we fire a canon, the sound will expand in spheres with a finite speed and reach the listener nearby almost immediately, while a listener (not too) far away will only hear the sound seconds later. The speed of propagation is limited by the speed of sound.
Parabolic. An example is the diffusion equation, which describes how e.g. heat is transported within some media.
If at a specific timet0at one point, a rod is heated at the middle, that will have an immediate effect on the temperature at the entire rod.
The effect is only fromt0and forward, not for time beforet0.
Elliptic. This is for example the Laplace or Poisson equation. It often is used to describe a steady state, for example the steady state form of an elastic surface fixed at the boundary, e.g. a soap film.
If at one point some extra weight is added to the surface, or some points at the fixed boundary is moved down, this will force down the surface at all points.
System including time as one of the dimensions are never elliptic, since we cannot change the past. Such systems can at most be parabolic.
A
P P E N D I XF Implementation
This appendix will list two Matlab functions, the two basic steps of the BDD method: The matrix vector product (6.12), and the BDD precon-ditioner in equations (6.21).
Also a list of Matlab files, that have been used throughout the project is given, with a short description of the use. This is mostly for my own reference.
F.1 Matrix vector product,
Sufunction Su=Sufun(u_B,A_II,A_IB,A_BI,A_BB,A_i,Rt,D,A0,Rt0,n_block,Rs) Su = zeros(size(u_B));
for i=1:n_block
Su = Su + Rt{i}*(A_BB{i}*(Rt{i}’*u_B));
Su = Su - Rt{i}*(A_BI{i} * ( A_II{i} \ (A_IB{i}*(Rt{i}’*u_B)) ));
end
150 Implementation