Spectra and Pseudospectra of Waveform Relaxation Operators.
We describe the spectra and pseudospectra of continuous time and discrete time waveform relaxation operators.  Since the spectrum of the finite-interval waveform relaxation operator is only a singleton, the spectrum of the infinite-interval operator is typically used to describe the behavior of waveform relaxation algorithms.  Here, we show that the pseudospectrum is a more useful tool for analyzing convergence of waveform iterations on finite intervals and prove that the pseudospectrum of the infinite-interval operator is in fact the limit of the pseudospectra of the finite-interval operators.
Introduction
. The waveform relaxation algorithm is a dynamic iteration method for
solving initial boundary-valueproblems, typically in ordinary differential equations or differential-algebraic
equations [11, 23]. Although the method has been widely used for some time,
very few rigorous results regarding the convergence of waveform relaxation methods have
appeared. This is due, in part, to the fact that practical initial value problems are solved on
finite time intervals, where the waveform relaxation operator has a spectrum consisting only
of a singleton, f0g. The most detailed analysis of waveform relaxation [14] instead analyzed
waveform relaxation applied to initial value problems on the infinite interval, [0; 1), in which
case the spectrum is meaningful for analyzing convergence.
The infinite-interval results are typically used with some justification about "sufficiently
long intervals." However, the spectrum of the finite interval operator is always a singleton,
regardless of the length of the interval so that the limit of the spectrum of the finite-interval operator
is not the spectrum of the infinite-interval operator. Yet, in practice, the infinite-interval
results often are in fact good predictors of finite-interval behavior.
That the spectrum of the finite-interval operator is not a good predictor of the convergence
of WR iterations is due to the fact that the waveform relaxation operator on a finite interval is
highly non-normal. For non-normal operators, the so-called pseudospectrum has been shown
to be a more useful tool than the spectrum for determining the behavior of iterative methods
applied to non-normal operators [18, 19, 21]. Roughly speaking (and we will be more precise
below), the spectrum of an operator is the region in the complex plane where the norm of the
resolvent of an operator is infinite, whereas the pseudospectrum is the region in the complex
plane where the norm of the resolvent is large, but not necessarily infinite.
In this paper, we use the pseudospectrum to relate the finite-interval behavior of wave-form
relaxation to the behavior predicted by the infinite-interval theory. In fact, we show that,
although the limit of the spectrum of the finite-interval operator is not the same as the spectrum
of the infinite-interval operator, the limit of the pseudospectrum of the finite-interval operators
is the same as the spectrum of the infinite-interval operator and that the spectrum and pseu-
dospectrum of the infinite interval operator are closely related.
The following definitions will be used in the sequel, as we investigate the spectral and
pseudospectral properties of waveform relaxation operators. We begin with a formal definition
Submitted for publication June 14, 1995. This work was supported in part by National Science Foundation
grant CCR92-09815.
y Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556,
z Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556,
A. Lumsdaine & D. Wu
of the spectrum of a bounded operator on a Banach space [5].
DEFINITION 1.1. Let Xbe a Banach space. The spectrum of a bounded operator A :
X!Xis defined as
Next, we define the ffl-pseudospectrum of a densely defined closed linear operator in a Banach
space [20, 18].
DEFINITION 1.2. Let Xbe a Banach space with norm k \Delta k. The ffl-pseudospectrum of a
densely defined closed linear operator A : X!Xis defined as
The pseudospectrum is sometimes also defined as
where it is understood that k(-I \Gamma
In this paper, we will be presenting results for the spectra and pseudospectra of continuous-
and discrete-time waveform relaxation operators. The continuous-time waveform relaxation
operators have quite a bit in common with Wiener-Hopf integral operators. In [1], Anselone
and Sloan studied spectral approximations for Wiener-Hopf operators on the space L 1
C[0; 1): The pseudospectra of Wiener-Hopf operators were studied by Reddy [18] and more
recently by B-ottcher [3]. The discrete-time waveform relaxation operators are in fact lower-triangular
block Toeplitz matrices. Here, we extend the Toeplitz matrix results of Reichel and
Trefethen [19] to the specific case of discrete-time waveform-relaxation operators.
2. Waveform Relaxation. A mathematical description of waveform relaxation can be
developed through the use of a model linear initial value problem (IVP):
d
(1)
where A(t) 2 R n\Thetan , f(t) 2 R n , and x(t) 2 R n is the unknown vector to be computed over
an interval of interest, t 2 [0; T ].
A waveform relaxation algorithm for this process is described by:
ALGORITHM 2.1 (JACOBI WAVEFORM RELAXATION).
1. Start: Select initial value x 0 (t) for t 2 [0; T ].
2. Iterate: For each waveform iteration
For each equation solve the IVP:
d
dt x k+1
Here, at every waveform iteration k, each equation in the system is solved for its corresponding
component of x, using previous values of the other components as input. Note that
the left hand side uses only the diagonal element of A (i.e., a ii for the computation of x i (t)).
The structure of this process is analogous to that of Gauss-Jacobi relaxation for solving linear
systems of equations [22]; hence, this particular decomposition and solution process is usually
called Alternative decompositions can be constructed (e.g.,
Seidel), based on alternative splittings of the matrix A.
Spectra and Pseudo-Spectra of Waveform Relaxation Operators 3
In (1), let be a splitting of A. The waveform relaxation algorithm based
on this splitting is expressed in matrix form as
ALGORITHM 2.2 (WAVEFORM RELAXATION FOR LINEAR SYSTEMS).
1. Initialize: Pick x 0
2. Iterate: For waveform iteration
Solve d
x
for x k+1 (t) on [0; T ].
We can solve for x k+1 (t) explicitly [8], that is,
x
(2)
s) is the transition matrix of M [4]. Using operator notation, we can write (2)
as
where the variables are defined on a suitable function space. The operator K is defined as
and / is given by
Based on the splitting of A, the solution x to (2) will satisfy
d
Or, using operator notation, we can see that x will satisfy
where I is the identity operator.
The standard waveform relaxation algorithm (3) is obtained from (4) by applying the
Richardson iteration [22]:
In the integral equation literature, this approach is also known as the method of successive
approximations [2, 10, 12].
Remark. Particular choices of M produce familiar iterations. E.g., taking results
in the Picard iteration [6, 17] and taking M to be the diagonal part of A results in the Jacobi
WR algorithm (Algorithm 2.1).
3. The Continuous Time Waveform Relaxation Operator. Let M (t) and N (t) be
constant matrices. Then \Phi that (2) can be written as
x
Z te \GammaM (t\Gammas)
ds:
4 A. Lumsdaine & D. Wu
The spectral properties of this operator on the half infinite interval were studied extensively
in [14]. In this section, we review the spectral properties of the continuous time waveform
relaxation operator on both finite and infinite intervals and derive expressions for the pseudospectra

First, we introduce some notation to distinguish the finite and infinite interval operators.
Define the infinite interval operator according to
Z te \GammaM (t\Gammas) Nf (s)ds;
and the finite interval operator according to
Z te \GammaM (t\Gammas) Nf(s)ds:
Note that the expression of the operators K1 and K T is the same - it is the space they act
on that differs. In conjunction with these operators we also define their matrix-valued symbol
K(z) by
We assume hereafter that M and N are constant n \Theta n matrices and that M has eigenvalues
with positive real parts, i.e., that K1 is a bounded operator.
3.1. The Infinite Interval Case. We consider first the waveform relaxation operator on
the infinite interval, K1 . The following result concerning the spectrum of K1 can be found
in [14].
THEOREM 3.1. If M andN are constant matrices, and M has eigenvalues with positive
real parts, then K1 has spectrum
cl
Re z-0
There is a simple geometric interpretation of Theorem 3.1 for a specific, but large, class
of problems.
PROPOSITION 3.2. Let let N be diagonalizable.
Then,
ae
Re d
Re d
oe
d are the eigenvalues of M \Gamma1 N . That is, the spectrum of the operator is a union of
discs, with disc j having radius j - j
Red
and centered at - j
2Red
. The boundary of the disc will
intersect f0g and the jth eigenvalue of M \Gamma1 N .
Theorem 3.1 states that the spectrum of the operator K1 is the spectrum of its matrix symbol
K(z) as z ranges over the right half-plane. Interestingly, the same basic property holds for
the pseudospectrum. The pseudospectrum of K1 is the pseudospectrum of its matrix symbol
K(z) as z ranges over the right half-plane. To obtain this result, we use the followinglemmas.
LEMMA 3.3. If M and N are constant matrices, and M has eigenvalues with positive
real parts, then K1 satisfies
Spectra and Pseudo-Spectra of Waveform Relaxation Operators 5
Proof. To prove the lemma, it is sufficient to show that there exists w
such that 1
Note first the following
For any u 2 C n , and z with Re z - 0, define
N)t
N)s dsN
w(t)
w(t)
As an immediate consequence, we have,
COROLLARY 3.4. For " ? 0,
Re z-0
LEMMA 3.5. In L 2 norm,
Re z=0
Proof. By using Fourier transform techniques, it is straightforward to show that
Re z=0
But since we also have k (-I
must hold.
THEOREM 3.6. If M andN are constant matrices, and M has eigenvalues with positive
real parts, then K1 has a pseudospectrum satisfying
cl
Re z-0
We abuse notation here for the sake of clarity and indicate A
6 A. Lumsdaine & D. Wu
Proof. If Lemma 3.5, this implies that
cl
But, by Corollary 4.3, this inclusion must in fact be an equality.
3.2. The Finite Interval Case. We consider next the waveform relaxation operator on
the finite interval, K T . The following is a standard result, since the kernel is in L 2 and the
integral is of Volterra type (see, e.g., [10]).
THEOREM 3.7. If M and N are piecewise continuous with respect to t 2 [0; T ], then
KT is compact and has a spectrum consisting only of the singleton f0g:
We do not obtain a precise expression for the pseudospectrum in this case, rather we obtain
upper and lower bounds. It is useful first to establish the net property of   " (KT ).
LEMMA 3.8. If
Proof. This follows directly from the observation that
THEOREM 3.9. If M and N are constant matrices, then K T has pseudospectrum satisfying

Proof. The first inclusion is obtained by realizing that [9]
The second inclusion is an immediate consequence of Lemma 3.8.
3.3. Relationship Between the Finite and Infinite Interval Operators. It is clear from
the preceding that in the limit of infinitely long intervals, the spectrum of K T does not converge
to the spectrum of K1 , i.e.,
lim
However, it is the case that the pseudospectrum converges.
THEOREM 3.10. For " ? 0,
cl lim
From Lemma 3.8, we see that f  " (K T )g has the net property with respect to T . There-
fore, lim T!1
LEMMA 3.11. In L 2 norm,
lim
Proof. By Lemma 3.8, we have seen that
lim
Spectra and Pseudo-Spectra of Waveform Relaxation Operators 7
Next, we want to prove that
lim
Case 1.
operator. By the definition of supremum, for any m,
By letting n !1; and since f m 2 L 2 [0; 1), lim n!1 kfm k 2
Let m !1; we obtain
lim
Case 2. - 2  (K 1
We have to prove that lim T!1 is an unbounded
operator. For any n 2 N; choose f
i.e.,
lim
Then
Therefore lim
Proof (of the Theorem).
cl lim T!1   " (K T
8 A. Lumsdaine & D. Wu
i.e.,
Let T !1; we see that
letting we get that   " (K1 Hence, the theorem follows by
Lemma 3.8.
Remark. Since   " (K T ) has the net property,
lim
which may not be closed. Therefore, we take the closure.
4. The Discrete Time Waveform Relaxation Operator. In practice, the solution step
in Algorithm 2.1 would be accomplished with an s-step linear multistep integration formula
and so it is important to understand the characteristics of the spectra and pseudospectra of
discretized WR operators. The application of an s-step linear multistep formula (referred to
hereafter simply as "multistep formula") produces the following discretized WR iteration:
s
s
s
s
Here, x k [i] 2 C n denotes value of x at timestep i at waveform iterate k and is the discrete
approximation to x k We will assume hereafter that discretized waveforms are either
members of a suitable sequence space ' 2 in the infinite interval case or that they are bounded
sequences in the finite interval case.
Using the difference equation
s
s
s
we construct the usual polynomials
s
s
The linear mappings v 7! w are denoted by K T or K1 in the finite and infinite interval
cases, respectively, and the symbol of both K T and K1 is given by
~
ae
oe
(z)I +M
ae
oe
Spectra and Pseudo-Spectra of Waveform Relaxation Operators 9
A useful tool for analyzing discrete time WR operators is to consider them in matrix form.
Define the lower-triangular Toeplitz matrices (operators, for the infinite-interval case)
. ff 0
. 0
. fi 0
. 0
Then, as matrices, K T and K1 are written as
where M and N are the block Toeplitz matrices given by
Here,
denotes the Kronecker product of A and B. To distinguish the finite and infinite
interval cases, we will denote the corresponding matrices as K T and K1 , respectively.
In the following sections we make extensive use of the matrix representation of K T and
K1 . Although the results given follow directly from the theory of spectra and pseudospectra
of triangular block Toeplitz matrices [13], we provide more specific proofs below. Analysis of
the spectrum (but not the pseudospectrum) discrete time WR relaxation operators was considered
in [16] and [15] for the finite and infinite-interval cases, respectively. Some of the results
are restated below (but we provide alternate proofs). We assume hereafter that M and N are
constant and that the eigenvalues of M are in the stability region of the multistep method, i.e.,
that K1 is a bounded operator.
4.1. The Infinite Interval Case. In the infinite interval case, the spectrum of K1 will
consist of more than simply eigenvalues, as the following theorem illustrates.
THEOREM 4.1. The spectrum of K1 is given by
cl

~
K(z)
Proof. Clearly, only if an eigenvalue of the matrix
lies
outside the stability region of the multistep method (or eigenvalues with multiplicity greater
than one lie on the boundary). That is, - 2   (K1 ) if and only if for some - such that
det
there exists some z with jzj - 1 that satisfies
Substituting
ae(z)
oe(z) into (5), and rewriting, we have
det
ae
oe
K(z)
A. Lumsdaine & D. Wu
Thus, - is also in the spectrum of ~
K(z). Using the same reasoning, it is easy to show that
- 62   (K1 ) implies that - is not in the spectrum of ~
K(z).
Thus, the spectrum of K1 is the spectrum of its matrix symbol ~
K(z) as z ranges outside
the unit disc. As with the continuous-timeoperator, the same basic property holds for the pseu-
dospectrum. The pseudospectrum of K1 is the pseudospectrum of its matrix symbol ~
K(z)
as z ranges outside the unit disc. We use the following lemmas to obtain this result.
LEMMA 4.2. In L 2 norm, and for jzj - 1,
K(z)
Proof. To prove the lemma, it is sufficient to show that there exists u and v such that
K(z)
note that ff T
z \Gammas oe(z)u. Rewrite
K(z)
K(z)
ae
oe
ae
oe
If we assume
ae
oe
then
(u\Omega ~
ae
oe
u\Omega v:
Therefore,
u\Omega ~
v:
Thus,
(u\Omega ~
ae
oe
~
K(z)
Spectra and Pseudo-Spectra of Waveform Relaxation Operators 11
As an immediate consequence, we have,
COROLLARY 4.3. For " ? 0,
~
K(z)
LEMMA 4.4. The following equality holds,
K(z)
k:
Proof. By using Fourier transform techniques, it is straightforward to show that
K(z)
k:
But since we also have k
K(z)
must hold.
THEOREM 4.5. The pseudospectrum of K1 is given by
cl
~
K(z)
Proof. If Lemma 4.4, this implies that
~
for some z 0 . Thus,
cl
~
K(z)
But, by Corollary 4.3, this inclusion must in fact be an equality.
4.2. The Finite Interval Case. Since M T and N T are both lower-triangularblock Toeplitz
and finite-dimensional, we can readily state the following:
THEOREM 4.6. The spectrum of K T is given by
I\Omega M
~
LEMMA 4.7. If
Proof. This follows directly from the observation that for
THEOREM 4.8. If M ; N 2 C n\Thetan are constant matrices, then K
pseudospectrum satisfying:
r

K(z)
A. Lumsdaine & D. Wu
where
c s
s
Proof. The first inclusion is similar to one given in [7], which is the block extension of
the result for upper-triangular Toeplitz matrices in [19]. To prove the first inclusion, we show
r

~
K(z)
r

~
K(z)
and let v be the corresponding
eigenvector. Define
u\Omega v. Then it is easy to show
that
The second inclusion is an immediate consequence of Lemma 4.7.
4.3. Relationship Between the Finite and Infinite Interval Operators. As we had with
the continuous time WR operators, in the limit of infinitely long intervals, the spectrum of K T
does not converge to the spectrum of K1 , i.e.,
lim
However, it is again true that the pseudospectrum converges.
LEMMA 4.9. The following equality holds,
lim
Proof. The inequality lim obvious. We
need only to prove that
lim
which could be done by following the proof of Lemma 3.11. We give a simpler proof here.
For an infinite dimensional vector um = [u
~
where each umk is an n-dimensional vector. Then, lim k!1 u um and
kum k
lim
lim
k~
lim
As a consequence we have
COROLLARY 4.10. For " ? 0, lim T!1   " (K T
Spectra and Pseudo-Spectra of Waveform Relaxation Operators 13
5. Numerical Experiments. Although the results in the Sections 3 and 4 give us some
elegant expressions for the spectra and pseudospectra of waveform relaxation operators, their
graphical representations are truly beautiful. In this section we graph the spectra and pseudospectra
of some example problems.
For our numerical experiments we consider the model problem
d
We will consider two cases. In the first case, we take A to be a normal matrix:
A =\Deltax
which is obtained, e.g., from discretizing the one-dimensional heat equation with spatial discretization\Deltax . In the second case, A is given by
A =\Deltax
and was so chosen because of the interesting pseudospectrum of the resulting matrix M \Gamma1 N
(inspired by [19]). For all examples, we take use a Jacobi splitting
to obtain M and N from A, and we take
All experiments were conducted using matlab. Finite matrix spectra were computed using
matlab's internal eigenvalue routine. Finite matrix pseudospectra were obtained by repeatedly
times) computing the eigenvalues of the given matrix plus some random perturbation E
". The spectrum of K1 was computed by using the geometric interpretation of
Proposition 3.2 (the spectrum of K trivially). The pseudospectrum
of K1 was computed using the relationship in Theorem 3.6. That is, the pseudoeigenval-
ues of K(z) were computed for 320 sampled values of z along the imaginary axis. For the
discrete-time operators, the spectrum and pseudospectrum of K1 were computed using the
relationships in Theorem 4.1 and Theorem 4.5, respectively. That is, the eigenvalues (respec-
tively, pseudoeigenvalues) of ~
K(z) were computed for 128 sampled values of z along the unit
circle. The spectrum and pseudospectrum of K T were computed directly.

Figure

1 shows the spectrum and pseudospectrum for the matrix given in (6). The eigen-values
and pseudoeigenvalues of M \Gamma1 N are indicated with x and respectively. Since the
normal, the pseudospectrum is very close to the spectrum (in fact,   " (M

Figure

2 shows the spectra and pseudospectra of K T and K1 for A given in (6). Since
the matrix M \Gamma1 N is normal, the pseudospectrum of K1 is is also very close to the spectrum.

Figure

3 shows the spectra and pseudospectra of K T and K1 for A given in (6). Here,
we used BDF(4) discretization with 9 timepoints and took 1. Again, since the matrix
is normal, there is close agreement between  (K 1 ) and   " (K T ), although
since numerical integration is non-normal, there is not close agreement between  (K T ) and

Figure

4 shows the spectra and pseudospectra of K T and K1 for A given in (6). Here,
we used BDF(4) discretization with timepoints and took This figure shows the
dramatic effect of stepsize on the spectrum and pseudospectrum of K1 . The spectrum and
pseudospectrum occupy a much larger region in the complex plane than that with 9 timepoints
14 A. Lumsdaine & D. Wu
-0.4
FIG. 1. Spectrum and pseudospectrumof M \Gamma1 N , using Jacobi splitting, for matrix A given in (6). The eigen-values
and pseudoeigenvalues of M \Gamma1 N are indicated with x and
-0.4
-0.4
FIG. 2. Spectrum and pseudospectrum of K T and K1 for A given in (6). In the left figure,  (K 1 ) is the
union of the interiors of the circles shown,  (K T ) is indicated with o, and the eigenvalues of M \Gamma1 N are indicated
with x. In the right figure, sampled values of the boundary of   " (K1 ) are shown as dots.
(as shown in Figure3). Because of the large number of timepoints, the matrix K T was too
large for us to be able to directly compute the actual spectrum or pseudospectrum. Naturally,
however, the pseudospectrum of K1 is an upper bound for   " (K T ). The degree to which
actually conforms to   " (K1 ) will depend on the size of T , as illustrated in the next
figure.

Figure

5 shows the spectra and pseudospectra of K T and K1 for A given in (6). Here,
we used BDF(4) discretization with 9 timepoints and took 1. Note that the region enclosed
by   " (K T ) is much larger for 1. In the expanded view of
the spectrum of K T , it is evident that the computed eigenvalues of K T are smeared. This
is due to the fact that, in finite-precision arithmetic, computed eigenvalues are actually the
pseudoeigenvalues with " equal to machine precision. (The reader is cautioned here against
thus assuming that the pseudospectrum is in any way a tool for analyzing the effects of finite
Spectra and Pseudo-Spectra of Waveform Relaxation Operators 15
-0.4
-0.4
FIG. 3. Spectrum and pseudospectrum of K T and K1 with BDF(4) discretization for A given in (6). In the
left figure,  (K 1 ) is the union of the interiors of the "beans" shown, the eigenvalues of of K T are indicated with
and the eigenvalues M \Gamma1 N are indicated with x. In the right figure, sampled values of the boundary of   " (K1 )
are shown as dots and are the large "bean" shapes. Inside of each "bean" are dots representingthe pseudospectrum
of K T . The computed eigenvalues of K T are indicated with +.
precision computations - it is a much more sublime tool than that.)

Figure

6 shows the spectra and pseudospectra of K T and K1 for A given in (6). Here,
instead of BDF(4), we used BDF(1) discretization with 9 timepoints and took
that the region enclosed by the spetrum and pseudospectrum of K1 is differently shaped (and
smaller) than with BDF(4).
-0.4
-0.4
FIG. 4. Spectrum and pseudospectrum of K T and K1 with BDF(4) discretization for A given in (6), using
a small timestep. In the left figure,  (K 1 ) is the union of the interiors of the "beans" shown, the eigenvalues of of
K T are indicated with o and the eigenvalues M \Gamma1 N are indicated with x. In the right figure, sampled values of
the boundary of   " (K1 ) are shown as dots.

Figures

duplicate the experiments shown in Figures 1 through 3 for the matrix
A given in (7). These figures are particularly striking because the non-normality of both
the matrix and the integration appear graphically. Note especially in Figure 8 how the "propel-
A. Lumsdaine & D. Wu
-0.4
-0.4
-0.3
-0.2
FIG. 5. Spectrum and pseudospectrum of K T and K1 with BDF(4) discretization for A given in (6), using
a longer time interval. In the left figure, sampled values of the boundary of   " (K1 ) are shown as dots and are
the large "bean" shapes. Inside of each "bean" are dots representing the pseudospectrum of K T . The computed
eigenvalues of K T are indicated with +. In the right figure, we show a close up of the right half of the left figure.
-0.4
-0.4
FIG. 6. Spectrum and pseudospectrum of K T and K1 with BDF(1) discretization for A given in (6). In the
left figure,  (K 1 ) is the union of the interiors of the "beans" shown, the eigenvalues of of K T are indicated with
and the eigenvalues M \Gamma1 N are indicated with x. In the right figure, sampled values of the boundary of   " (K1 )
are shown as dots and are the large "bean" shapes. Inside of each "bean" are dots representingthe pseudospectrum
of K T . The computed eigenvalues of K T are indicated with +.
lor" shape of the matrix pseudospectrum as well as the "flower" shape of  (K 1 ) are evident in
the illustration of   " (K1 ). Contrast this with Figure 2, where the spectrum and pseudospec-
trum of K1 are essentially the same.

Acknowledgments

. The authors would like to acknowledge helpful discussions with
Nick Trefethen, Satish Reddy, Ken Jackson, Stefan Vandewalle, and Jan Janssen. The authors
are especially grateful to Nick Trefethen for providing preprints of his book Spectra and
Pseudospectra: The Behavior of Non-Normal Matrices and Operators.
Spectra and Pseudo-Spectra of Waveform Relaxation Operators 17
-0.4
FIG. 7. Spectrum and pseudospectrumof M \Gamma1 N , using Jacobi splitting, for matrix A given in (7). The eigen-values
and pseudoeigenvalues of M \Gamma1 N are indicated with x and
-0.4
-0.4
FIG. 8. Spectrum and pseudospectrum of K T and K1 for A given in (7). In the left figure,  (K 1 ) is the
union of the interiors of the circles shown,  (K T ) is indicated with o, and the eigenvalues of M \Gamma1 N are indicated
with x. In the right figure, sampled values of the boundary of   " (K1 ) are shown as dots.
A. Lumsdaine & D. Wu
-0.4
FIG. 9. Spectrum of K T and K1 with BDF(4) discretization for A given in (7). Here,  (K 1 ) is the union
of the interiors of the "beans" shown, the eigenvalues of of K T are indicated with o and the eigenvalues M \Gamma1 N
are indicated with x.
-0.4
-0.4
FIG. 10. Pseudospectrum of K T and K1 with BDF(4) discretization for A given in (7). In the left figure,
sampled values of the boundaryof   " (K1 ) are shown as dots. The right figure shows the computedpseudospectrum
of K T , indicated with dots. The computed eigenvalues of K T are indicated with +.
Spectra and Pseudo-Spectra of Waveform Relaxation Operators 19



--R

Spectral approximations for Wiener-Hopf operators
A Survey of Numerical Methods for the Solution of Fredholm Integral Equations of the Second Kind

Finite Dimensional Linear Systems
A Course in Functional Analysis
Dynamical Systems
Convergence analysis of waveform relaxation methods using pseudospec- tra
Linear Systems
Perturbation Theory for Linear Operators

The waveform relaxation method for time domain analysis of largescale integrated circuits
Analytical and Numerical Methods for Volterra Equations
Spectra and pseudospectra of block Toeplitz matrices
Convergence of dynamic iteration methods for initial value problems

Remarks on Picard-Lindel-of iteration

Pseudospectra of operators and discretization matrices and an application to stability of the method of lines
Eigenvalues and pseudo-eigenvalues of Toeplitz matrices
Spectra and pseudospectra: The behavior of non-normal matrices and operators

Matrix Iterative Analysis
Relaxation Techniques for the Simulation of VLSI Cir- cuits
--TR
dynamic iteration;pseudospectrum;waveform relaxation;spectrum