\documentstyle{siamltex}
\begin{document}
\renewcommand{\thepage}{\roman{page}}
\LARGE
\begin{flushleft}
Electronic Transactions on Numerical Analysis \\
Volume 1, 1993
\end{flushleft}
\setlength{\unitlength}{1in}
\begin{picture}(6,.5)
\linethickness{.25in}
\put(0,.25){\line(1,0){5.5}}
\end{picture}
Contents
\medskip
\normalsize
\begin{description}
\labelwidth .4in
\item[1~~~]
Analysis of the linearly implicit mid--point rule for
differential--algebraic equations.
{\em Claus Schneider.}
\medskip
\noindent
{\bf Abstract.}
The error of the linearly implicit mid--point rule after $2m+1$ steps
is expanded in powers of $m^2$. We prove that the well-known expansion
for ordinary differential equations (an expansion in negative powers
of $m^2$) is perturbed by additional terms with non-negative powers of
$m^2$ for semi--explicit differential--algebraic equations of index one.
Hence, extrapolation in $m^{-2}$ will be of limited value only. The
complete expansion shows these limits and, furthermore, can be used to
derive an order 8 method of Rosenbrock type.
\medskip
\noindent
{\bf Key words.}
Differential--algebraic equations, linearly implicit mid--point rule,
Rosenbrock--type methods, extrapolation.
\medskip
\noindent
{\bf AMS(MOS) subject classification.}
65L05, 65B05, 58F99.
\medskip
\noindent
{\bf Files.}
vol.1.1993/pp1--10.ps
\medskip
\noindent
{\bf Forward References.}
\medskip
\item[11~~]
BiCGstab($l$) for linear equations involving unsymmetric matrices with
complex spectrum.
{\em Gerard L.G. Sleijpen and Diederik R. Fokkema.}
\medskip
\noindent
{\bf Abstract.}
For a number of linear systems of equations arising from realistic
problems, using the Bi-CGSTAB algorithm of van der Vorst to solve these
equations is very attractive. Unfortunately, for a large class of equations,
where, for instance, Bi-CG performs well, the convergence of Bi-CGSTAB
stagnates. This was observed specifically in case of discretized advection
dominated PDE's. The stagnation is due to the fact that for this type of
equations the matrix has almost pure imaginary eigenvalues. With his
BiCGStab2 algorithm Gutknecht attempted to avoid this stagnation. Here, we
generalize the Bi-CGSTAB algorithm further, and overcome some shortcomings
of BiCGStab2. In some sense, the new algorithm combines GMRES($l$) and
Bi-CG and profits from both.
\medskip
\noindent
{\bf Key words.}
Bi-conjugate gradients, non-symmetric linear systems, CGS, Bi-CGSTAB,
iterative solvers, GMRES, Krylov subspace.
\medskip
\noindent
{\bf AMS(MOS) subject classification.}
65F10.
\medskip
\noindent
{\bf Files.}
vol.1.1993/pp11--32.ps
\medskip
\noindent
{\bf Forward References.}
\newpage
\item[33~~]
A multishift algorithm for the numerical solution of algebraic Riccati
equations.
{\em Gregory Ammar, Peter Benner, and Volker Mehrmann.}
\medskip
\noindent
{\bf Abstract.}
We study an algorithm for the numerical solution of algebraic matrix
Riccati equations that arise in linear optimal control problems.
The algorithm can be considered to be a multishift technique, which uses
only orthogonal symplectic similarity transformations to compute
a Lagrangian invariant subspace of the associated Hamiltonian matrix.
We describe the details of this method and compare it with other
numerical methods for the solution of the algebraic Riccati equation.
\medskip
\noindent
{\bf Key words.}
algebraic matrix Riccati equation, Hamiltonian matrix, Lagrangian
invariant subspace.
\medskip
\noindent
{\bf AMS(MOS) subject classification.}
65F15, 15A24, 93B40.
\medskip
\noindent
{\bf Files.}
vol.1.1993/pp33--48.ps
\medskip
\noindent
{\bf Forward References.}
\medskip
\item[49~~]
Zeros and local extreme points of Faber polynomials associated with
hypocycloidal domains.
{\em Michael Eiermann and Richard S. Varga.}
\medskip
\noindent
{\bf Abstract.}
Faber polynomials play an important role in different areas of constructive
complex analysis. Here, the zeros and local extreme points of Faber
polynomials for hypocycloidal domains are studied. For this task, we use
tools from linear algebra, namely, the Perron-Frobenius theory of
nonnegative matrices, the Gantmacher-Krein theory of oscillation matrices,
and the Schmidt-Spitzer theory for the asymptotic spectral behavior of
banded Toeplitz matrices.
\medskip
\noindent
{\bf Key words.}
Faber polynomials, cyclic of index $p$ matrices, oscillation matrices.
\medskip
\noindent
{\bf AMS(MOS) subject classification.}
30C15, 15A48, 15A57.
\medskip
\noindent
{\bf Files.}
vol.1.1993/pp49--71.ps
\medskip
\noindent
{\bf Forward References.}
\medskip
\item[72~~]
Numerical Methods for the Computation of Analytic Singular Value
Decompositions. {\em Volker Mehrmann and Werner Rath.}
\medskip
\noindent
{\bf Abstract.}
An analytic singular value decomposition (ASVD) of a path of matrices
$E(t)$ is an analytic path of factorizations $E(t) = X(t) S(t) Y(t)^T$
where $X(t)$ and $Y(t)$ are orthogonal and $S(t)$ is diagonal. The
diagonal entries of $S(t)$ are allowed to be either positive or
negative and to appear in any order. For an analytic path matrix
$E(t)$ an ASVD exists, but this ASVD is not unique. We present
two new numerical methods for the computation of unique ASVD's. One
is based on a completely algebraic approach and the other on one step
methods for ordinary differential equations in combination with
projections into the set of orthogonal matrices.
\medskip
\noindent
{\bf Key words.}
analytic singular value decompostion, singular values decomposition.
\medskip
\noindent
{\bf AMS(MOS) subject classification.}
65F25.
\medskip
\noindent
{\bf Files.}
vol.1.1993/pp72--88.ps
\medskip
\noindent
{\bf Forward References.}
\medskip
\item[89~~]
A Chebyshev-like Semiiteration for Inconsistent Linear Systems.
{\em Martin Hanke and Marlis Hochbruck.}
\medskip
\noindent
{\bf Abstract.}
Semiiterative methods are known as a powerful tool for the iterative
solution of nonsingular linear systems of equations. For singular
but consistent linear systems with coefficient matrix of index one,
one can still apply the methods designed for the nonsingular case.
However, if the system is inconsistent, the approximations usually fail to
converge. Nevertheless, it is still possible to modify classical methods
like the Chebyshev semiiterative method in order to fulfill the additional
convergence requirements caused by the inconsistency.
These modifications may suffer from
instabilities since they are based on the computation of the diverging
Chebyshev iterates. In this paper we develop an alternative algorithm
which allows to construct more stable approximations. This algorithm can be
efficiently implemented with short recurrences. There are several
reasons indicating that the new algorithm is the most natural generalization
of the Chebyshev semiiteration to inconsistent linear systems.
\medskip
\noindent
{\bf Key words.}
Semiiterative methods, singular systems,
Zolotarev problem, orthogonal polynomials.
\medskip
\noindent
{\bf AMS(MOS) subject classification.}
65F10, 65F20.
\medskip
\noindent
{\bf Files.}
vol.1.1993/pp89--103.ps
\medskip
\noindent
{\bf Forward References.}
\medskip
\item[104~~]
A New Lehmer Pair of Zeros and a New Lower Bound for the
de Bruijn-Newman Constant {$\Lambda$}.
{\em G. Csordas, A.M. Odlyzko, W. Smith, and R. S. Varga.}
\medskip
\noindent
{\bf Abstract.}
The de Bruijn-Newman constant $\Lambda$ has been investigated extensively
because the truth of the Riemann Hypothesis is equivalent to
the assertion that $\Lambda \leq 0$. On the other hand, C. M. Newman
conjectured that $\Lambda \geq 0$. This paper improves previous
lower bounds by showing that
\[
-5.895 \cdot 10^{-9} < \Lambda.
\]
This is done with the help of a spectacularly close pair of
consecutive zeros of the Riemann zeta function.
\medskip
\noindent
{\bf Key words.}
Lehmer pairs of zeros, de Bruijn-Newman constant, Riemann Hypothesis.
\medskip
\noindent
{\bf AMS(MOS) subject classification.}
30D10, 30D15, 65E05.
\medskip
\noindent
{\bf Files.}
vol.1.1993/pp104-111.ps
\medskip
\noindent
{\bf Forward References.}
\medskip
\end{description}
%\end{document}
%Slit files here
\newpage
\LARGE
\begin{center}
ACCESSING ETNA \\
\end{center}
\normalsize
\vspace{.25in}
\begin{enumerate}
\item BECOMING A SUBSCRIBER TO ETNA.
To be included in ETNA's quarterly mailing list of the titles and abstracts
of papers published in ETNA, send an e-mail message to etna@mcs.kent.edu
with the subject ``ETNA Registration''. \\
\item ACCESSING ETNA USING GOPHER.
ETNA is running a gopher server. Its hostname is: \\
etna.mcs.kent.edu.
If you are running gopher on your system the command
gopher etna.mcs.kent.edu
will connect you directly to ETNA. Provided your system is suitably
configured, keyword searches and the on-line-graphical display of
papers will then be available. The ETNA directory, ``viewers'', contains
the source files for programs that will provide most UNIX workstations
with direct-display and keyword-search capabilities. Contact your system
administrator about installing these programs. \\
\item OBTAINING AN ETNA PAPER WITH FTP.
Papers can be obtained at any time from ETNA via anonymous ftp from
etna.mcs.kent.edu. A paper's location will always correspond to
its reference. For instance, a paper which is referenced as
``...,Elec. Trans. Numer. Anal., Vol 1, 1993, pp. 11-35'', will be stored
in the directory ``vol.1.1993'', and its file name will be ``pp11-35.ps''.
To obtain that paper using ftp
\begin{tabular}{rl}
& \\
a) & ftp etna.mcs.kent.edu \\
b) & login as anonymous \\
c) & enter your e-mail address as your password \\
d) & cd to vol.1.1993 \\
e) & get pp11-35.ps \\
& \\
\end{tabular}{rl}
To obtain only the list of titles and abstracts for the papers published
is volume 1 of ETNA, repeat a)-d) above but change e) to
e) get index \\
\item OBTAINING AN ETNA PAPER VIA E-MAIL.
ETNA is using a mailer program which will scan incoming e-mail messages
for requests and then e-mail the requested file to the sender. The program
was written by Eric Grosse for netlib and modified slightly by Arden
Ruttan for ETNA. \\
A PostScript file of any paper published in ETNA may be obtained by sending
an e-mail message to ``mailer@etna.mcs.kent.edu'' containing a phrase of the
form ``send pagenumber.ps from vol.number.year''. For instance, to use
ETNA's mailer to obtain a paper which is referenced as
``...,Elec. Trans. Numer. Anal., Vol 1, 1993, pp. 11-35'',
send e-mail to ``mailer@etna.mcs.kent.edu'' containing the phrase
``send pp11-35.ps from vol.1.1993''. \\
To obtain only the list of titles and abstract for the papers published
in volume 1 of ETNA, send an e-mail message to ``mailer@etna.mcs.kent.edu''
containing the phrase ``send index from vol.1.1993''. \\
The requested paper will be e-mailed to you in several pieces. The subject
of each piece of e-mail indicates the number of that piece. To
reconstruct the original file, \\
\begin{tabular}{rp{5in}}
a) & Edit each piece deleting all lines that are not strictly between
the two occurrence of the phrase ``CUT HERE............''
including the lines containing those phrases. \\
b) & Using the file containing piece 1, successively append
the remaining pieces in order to the END of the that file. \\
\end{tabular}
Unix users can also re-assemble the paper by removing the mail headers.
The resulting files are ``sh'' scripts which can reassembled by
issuing the commands (here we are assuming that the various parts
of the papers are stored in ``file1'', ``file2'',...,``filen'').
\begin{verbatim}
sh file1
sh file2
.
.
.
sh filen
\end{verbatim}
Unix users may also use the following script which will automatically
reconstruct the original PostScript file.
\begin{verbatim}
#!/bin/sh
# This is a shell script which will re-assemble the PostScript file
# mailed to you by ETNA's mailer program. To use this script
# 1) Copy this script to a file in an empty directory and name it reassm.
# 2) Save each mail message from ETNA with a unique name in the
# directory which contains this file.
# 3) Change to that directory and execute the command
# sh reassm
# or alternately you can
# 1) Change to a directory containing this a script in a file.
# 2) Save each mail message from ETNA with a unique name but with a common
# prefix shared by only the ETNA files. For example, you could save the
# respective ETNA files in ff1, ff2, ...
# 3) Assuming the name of this file is reassm, execute the command
# sh reassm ff
ls $1* | grep -v $0 > .f$$
for file in `cat .f$$`
do
echo $file
awk 'BEGIN{i=0};$1=="#!/bin/sh" {i=1};{if (i>0) print $0}' $file > .awk$$
/bin/sh .awk$$
done
rm .f$$
rm .awk$$
\end{verbatim}
\item SUBMITTING A PAPER TO ETNA.
To obtain information as to how to submit a paper to ETNA, ftp the file
``info-for-authors'' which is located in the directory ``etna-info''.
Alternately you may send an e-mail message to ``mailer@etna.mcs.kent.edu''
containing the phrase ``send info-for-authors from etna-info''.
\end{enumerate}
\end{document}
***********************************************
Electronic Transactions on Numerical Analysis
Volume 2, 1994
1. An implicitly restarted Lanczos method for large symmetric eigenvalue
problems. D. Calvetti, L. Reichel, and D.C. Sorensen.
Abstract.
The Lanczos process is a well known technique for computing a few, say
$k$, eigenvalues and associated eigenvectors of a large symmetric
$n\times n$ matrix. However, loss of orthogonality of the computed
Krylov subspace basis can reduce the accuracy of the computed
approximate eigenvalues. In the implicitly restarted Lanczos method
studied in the present paper, this problem is addressed by fixing the
number of steps in the Lanczos process at a prescribed value, $k+p$,
where $p$ typically is not much larger, and may be smaller, than $k$.
Orthogonality of the $k+p$ basis vectors of the Krylov subspace is
secured by reorthogonalizing these vectors when necessary. The
implicitly restarted Lanczos method exploits that the residual vector
obtained by the Lanczos process is a function of the initial Lanczos
vector. The method updates the initial Lanczos vector through an
iterative scheme. The purpose of the iterative scheme is to determine
an initial vector such that the associated residual vector is tiny. If
the residual vector vanishes, then an invariant subspace has been found.
This paper studies several iterative schemes, among them schemes based
on Leja points. The resulting algorithms are capable of computing a few
of the largest or smallest eigenvalues and associated eigenvectors. This
is accomplished using only $(k+p)n + O((k+p)^2)$ storage locations in
addition to the storage required for the matrix, where the second term
is independent of $n$.
Key words.
Lanczos method, eigenvalue, polynomial acceleration.
AMS(MOS) subject classification.
65F15.
Files.
vol.2.1994/pp1--21.ps
Forward References.
22. Multigrid Conformal Mapping via the Szeg\H{o} Kernel. Barry Lee and
Manfred R. Trummer.
Abstract.
We introduce a multilevel scheme to solve a second kind integral
equation which is important in computing conformal maps. This scheme
outperforms conjugate gradient methods previously employed for smooth
regions. An analysis of the two-grid scheme is provided.
Key words.
conformal mapping, multigrid, Szeg\H{o} kernel, integral equations.
AMS(MOS) subject classifications.
45L10, 45B05, 65R20, 65F20, 65F10.
Files.
vol.2.1994/pp22-43.ps
Forward References.
44. Displacement Preconditioner for Toeplitz Least Squares Iterations.
Raymond H. Chan, James G. Nagy, and Robert J. Plemmons.
Abstract.
We consider the solution of least squares problems $\min ||b-Ax||_2$
by the preconditioned conjugate gradient (PCG) method, for $m \times n$
complex Toeplitz matrices $A$ of rank $n$. A circulant preconditioner
$C$ is derived using the T. Chan optimal preconditioner for
$n \times n$ matrices using the displacement representation of $A^*A$.
This allows the fast Fourier transform (FFT) to be used throughout the
computations, for high numerical efficiency. Of course $A^*A$ need
never be formed explicitly. Displacement--based preconditioners have
also been shown to be very effective in linear estimation and adaptive
filtering. For Toeplitz matrices $A$ that are generated by
$2 \pi$-periodic continuous complex-valued functions without any zeros,
we prove that the singular values of the preconditioned matrix
$AC^{-1}$ are clustered around 1, for sufficiently large $n$. We show
that if the condition number of $A$ is of $O(n^\alpha)$, $\alpha >0$,
then the least squares conjugate gradient method converges in at most
$O(\alpha \log n+1)$ steps. Since each iteration requires only
$O(m \log n)$ operations using the FFT, it follows that the total
complexity of the algorithm is then only $O(\alpha m \log^2n +
m \log n)$. Conditions for {\em superlinear convergence} are given and
numerical examples are provided illustrating the effectiveness of
our methods.
Key words.
circulant preconditioner, conjugate gradient, displacement
representation, fast Fourier transform (FFT), Toeplitz operator.
AMS(MOS) subject classification.
65F10, 65F15.
Files.
vol.2.1993/pp44--56.ps
Forward References.
***********************************************
The contents of the June issue of ETNA is
Electronic Transactions on Numerical Analysis
Volume 2, 1994
57. Minimization properties and short recurrences for Krylov subspace
methods. Rudiger Weiss.
Abstract.
It is well known that generalized conjugate gradient (cg) methods,
fulfilling a minimization property in the whole spanned Krylov space,
cannot be formulated with short recurrences for nonsymmetric system
matrices. Here, Krylov subspace methods are proposed that do fulfill a
minimization property and can be implemented as short recurrence method
at the same time. These properties are achieved by a generalization of
the cg concept. The convergence and the geometric behavior of these
methods are investigated.
Practical applications show that first realizations of these methods are
already competitive with commonly used techniques such as smoothed
biconjugate gradients or QMR. Better results seem to be possible by
further improvements of the techniques. However, the purpose of this
paper is not to propagate a special method, but to stimulate research
and development of new iterative linear solvers.
Key words.
conjugate gradients, convergence, linear systems, Krylov methods.
AMS(MOS) subject classification.
65F10, 65F50, 40A05.
Files.
vol.2.1994/pp57--76.ps
Forward References.
76. Efficient iterative solution of linear systems from discretizing
singular integral equations. Ke Chen.
Abstract.
In this paper we study the solution of singular integral equations by
iterative methods. We show that discretization of singular integral
operators obtained by domain splitting yields a system of algebraic
equations that has a structure suitable for iterative solution.
Numerical examples of Cauchy type singular integral equations are
used to illustrate the proposed approach. This paper establishes a
theory for experimental results presented previously.
Key words.
singular integral equations, non-compact operators, direct solutions,
preconditioning, conjugate gradient iterative methods.
AMS(MOS) subject classification.
65F10, 65N38, 45E05.
Files.
vol.2.1994/pp76--91.ps
Forward References.
92. Modified Specht's plate bending element and its convergence analysis.
T.M. Shih and Junbin Gao.
Abstract.
This paper discusses Specht's plate bending element, shows the
relationships between $\int_{F_{\rho}}w\,ds$ or
$\int_{F_{\rho}}\frac{\partial w}{\partial n}\,ds$
and the nodal parameters (or degrees of freedom), further it sheds
lights on the construction methods for that element, and finally it
introduces a new plate bending element with good convergent properties
which passesthe F-E-M-Test is derived.
Key words.
interpolation, nonconforming finite element, Specht's element.
AMS(MOS) subject classification.
41A05, 65D05, 65N30.
Files.
vol.2.1994/pp92-103.ps.
Forward References.
***********************************************
Electronic Transactions on Numerical Analysis
Volume 2, 1994
This volume is dedicated to Wilhelm Niethammer
on the occasion of his 60th birthday.
104. Look-ahead Levinson- and Schur-type recurrences in the Pad\'e table.
Martin H. Gutknecht and Marlis Hochbruck.
Abstract.
For computing Pad\'e approximants, we present presumably stable
recursive algorithms that follow two adjacent rows of the Pad\'e
table and generalize the well-known classical Levinson and Schur
recurrences to the case of a nonnormal Pad\'e table. Singular blocks
in the table are crossed by look-ahead steps. Ill-conditioned Pad\'e
approximants are skipped also. If the size of these look-ahead steps is
bounded, the recursive computation of an $(m,n)$ Pad\'e approximant with
either the look-ahead Levinson or the look-ahead Schur algorithm
requires $O(n^2)$ operations. With recursive doubling and fast
polynomial multiplication, the cost of the look-ahead Schur algorithm
can be reduced to $O(n\log^2n)$.
Key words.
Pad\'e approximation, Toeplitz matrix, Levinson algorithm, Schur
algorithm, look-ahead, fast algorithm, biorthogonal polynomials,
Szeg\H{o} polynomials.
AMS(MOS) subject classifications.
41A21, 42A70, 15A06, 30E05, 60G25, 65F05, 65F30.
Files.
vol.2.1994/pp104-129.dir/pp104-129.ps.
Forward References.
130. The generalizations of Newton's interpolation formula due to M\"uhlbach
and Andoyer. C. Brezinski.
Abstract.
Newton's formula for constructing the interpolation polynomial is
well--known. It makes use of divided differences. It was generalized
around 1971--1973 by M\"uhlbach for interpolation by a linear family of
functions forming a complete Chebyshev system. This generalization rests
on a generalization of divided differences due to Popoviciu. In this
paper, it is shown that M\"uhlbach's formula is related to the work of
Andoyer which goes back to the beginning of the century.
Key words.
interpolation, divided differences, biorthogonality.
AMS(MOS) subject classifications.
65D05, 41A05.
Files.
vol.2.1994/pp130-137.dir/pp130-137.ps.
Forward References.
138. On the periodic quotient singular value decomposition. J.J. Hench.
Abstract.
The periodic Schur decomposition has been generally seen as a tool
to compute the eigenvalues of a product of matrices in a numerically
sound way. In a recent technical report, it was shown that the periodic
Schur decomposition may also be used to accurately compute the singular
value decomposition (SVD) of a matrix. This was accomplished by reducing
a periodic pencil that is associated with the standard normal equations
to eigenvalue revealing form. If this technique is extended to the
periodic QZ decomposition, then it is possible to compute the quotient
singular value decomposition (QSVD) of a matrix pair. This technique may
easily be extended further to a sequence of matrix pairs, thus computing
the ``periodic'' QSVD.
Key words.
singular value decomposition, periodic Schur decomposition, periodic
QR algorithm, periodic QZ algorithm, QSVD, SVD.
AMS(MOS) subject classifications.
15A18, 65F05, 65F15.
Files.
vol.2.1994/pp138-153.dir/pp138-153.ps.
Forward References.
***********************************************
The contents of the December issue of ETNA is
Electronic Transactions on Numerical Analysis
Volume 2, 1994
154. Fast iterative methods for solving Toeplitz-plus-Hankel least squares.
Michael K. Ng.
Abstract.
In this paper, we consider the impulse responses of the linear-phase
filter whose characteristics are determined on the basis of an
observed time series, not on a prior specification. The impulse
responses can be found by solving a least squares problem
$\min \| d - (X_1+X_2)w \|_2$ by the fast Fourier transform (FFT)
based preconditioned conjugate gradient method, for $(M+2n-1)$-by-$n$
real Toeplitz-plus-Hankel data matrices $X_1+X_2$ with full column rank.
The FFT--based preconditioners are derived from the spectral properties
of the given input stochastic process and their eigenvalues are
constructed by the Blackman-Tukey spectral estimator with Bartlett
window which is commonly used in signal processing. When the stochastic
process is stationary and its spectral density function is positive and
differentiable, we prove that with probability 1, the spectra of the
preconditioned normal equations is $O(M \log n)$ operations and each
iteration requires $O(n \log n)$ operations, the total complexity of
our algorithm is of order $O(M \log n + (2\alpha+1) n \log^2 n +
n \log n)$ operations. Finally, numerical results are reported to
illustrate the effectiveness of our FFT--based preconditioned iterations.
Key words.
least squares estimations, linear-phase filter, Toeplitz-plus-Hankel
matrix, circulant matrix, preconditioned conjugate gradient method,
fast Fourier transform.
AMS(MOS) subject classifications.
65F10, 65F15, 43E10.
Files.
vol.2.1994/pp154-170.dir/pp154-170.ps.
Forward References.
171. Domain decomposition and multigrid algorithms for elliptic problems on
unstructured meshes. Tony F. Chan and Barry F. Smith.
Abstract.
Multigrid and domain decomposition methods have proven to be versatile
methods for the iterative solution of linear and nonlinear systems of
equations arising from the discretization of partial differential
equations. The efficiency of these methods derives from the use of
a grid hierarchy. In some applications to problems on unstructured
grids, however, no natural multilevel structure of the grid is available
and thus must be generated as part of the solution procedure.
In this paper, we consider the problem of generating a multilevel grid
hierarchy when only a fine, unstructured grid is given. We restrict
attention to problems in two dimensions. Our techniques generate a
sequence of coarser grids by first forming a maximal independent set
of the graph of the grid or its dual and then applying a Cavendish type
algorithm to form the coarser triangulation. Iterates on the different
levels are combined using standard interpolation and restriction
operators. Numerical tests indicate that convergence using this
approach can be as fast as standard multigrid and domain decomposition
methods on a structured mesh.
Key words.
domain decomposition, grid refinement, multigrid, numerical partial
differential equations.
AMS(MOS) subject classifications.
65N30, 65F10.
Files.
vol.2.1994/pp171-182.dir/pp171-182.ps (Caution: 4.3mbytes--will not
print on many PostScript printers. Use the files listed below
unless you have a printer with a large memory.),
vol.2.1994/pp171-182.dir/pp171-176.ps (pages 171 to 176),
vol.2.1994/pp171-182.dir/pp177.ps (page 177),
vol.2.1994/pp171-182.dir/pp178-179.ps (pages 178 and 179),
vol.2.1994/pp171-182.dir/pp180.ps (page 180),
vol.2.1994/pp171-182.dir/pp181-182.ps (pages 181 and 182).
Forward References.
183. Convergence of infinite products of matrices and inner--outer iteration
schemes. Rafael Bru, L. Elsner, and M. Neumann.
Abstract.
We develop conditions under which a product $\prod_{i=0}^{\infty}T_{i}$
of matrices chosen from a possibly infinite set of matrices ${\cal S}=
\{T_j | j\in J\}$ converges. We obtain the following conditions which
are sufficient for the convergence of the product: There exists a vector
norm such that all matrices in ${\cal S}$ are nonexpansive with respect
to this norm and there exists a subsequence $\{i_k\}_{k=0}^{\infty}$
of the sequence of the nonnegative integers such that the corresponding
sequence of operators $\left\{ T_{i_k}\right\}_{k=0}^{\infty}$ converges
to an operator which is paracontracting with respect to this norm. We
deduce the continuity of the limit of the product of matrices as a
function of the sequences $\{i_k\}_{k=0}^{\infty}$. But more
importantly, we apply our results to the question of the convergence of
inner--outer iteration schemes for solving {\bf singular} consistent
linear systems of equations, where the outer splitting is regular
and the inner splitting is weak regular.
Key words.
iterative methods, infinite products, contractions.
AMS(MOS) subject classification.
65F10.
Files.
vol.2.1994/pp183-193.dir/pp183-193.ps.
Forward References.
194. Reducibility and characterization of symplectic Runge-Kutta methods.
Peter G\"{o}rtz and Rudolf Scherer.
Abstract.
Hamiltonian systems arise in many areas of physics, mechanics, and
engineering sciences as well as in pure and applied mathematics.
To their symplectic integration certain Runge--Kutta--type methods are
profitably applied (see Sanz--Serna and Calvo [10]). In this paper
Runge--Kutta and partitioned Runge--Kutta methods are considered.
Different features of symmetry are distinguished using reflected and
transposed methods. The property of DJ--irreducibility ensures
symplectic methods having nonvanishing weights. A characterization of
symplectic methods is deduced, from which many attributes of such
methods and hints for their construction follow. Order conditions up to
order four can be checked easily by simplifying assumptions. For
symplectic singly--implicit Runge--Kutta methods the order barrier is
shown to be two.
Key words.
Hamiltonian system, symplectic method, Runge--Kutta and partitioned
Runge--Kutta method, DJ--reducibility.
AMS(MOS) subject classification.
65L06.
Files.
vol.2.1994/pp194-204.dir/pp194-204.ps.
Forward References.
***********************************************
The contents of the March, 1995 issue of ETNA is
Electronic Transactions on Numerical Analysis
Volume 3, 1995
1. Orthonormal polynomial vectors and least squares approximation for a
discrete inner product. M. Van Barel and A. Bultheel.
Abstract.
We give the solution of a discrete least squares approximation problem
in terms of orthonormal polynomial vectors with respect to a discrete
inner product. The degrees of the polynomial elements of these vectors
can be different. An algorithm is constructed computing the coefficients
of recurrence relations for the orthonormal polynomial vectors. In case
the weight vectors are prescribed in points on the real axis or on the
unit circle, variants of the original algorithm can be designed which
are an order of magnitude more efficient. Although the recurrence
relations require all previous vectors to compute the next orthonormal
polynomial vector, in the real or the unit-circle case only a fixed
number of previous vectors are required. As an application, we
approximate a vector-valued function by a vector rational function in a
linearized least squares sense.
Key words.
orthonormal polynomial vectors, least squares approximation, vector
rational approximation.
AMS(MOS) subject classifications.
42C05, 30E10, 65D10, 41A28, 41A20.
Files.
vol.3.1995/pp1-23.dir/pp1-23.ps.
Forward References.
24. Parallel, synchronous and asynchronous two-stage multisplitting methods.
Rafael Bru, Violeta Migall, Jose Penades, and Daniel B. Szyld.
Abstract.
Different types of synchronous and asynchronous two-stage multisplitting
algorithms for the solution of linear systems are analyzed. The different
algorithms which appeared in the literature are reviewed, and new ones
are presented. Convergence properties of these algorithms are studied
when the matrix in question is either monotone or an $H$-matrix. Relaxed
versions of these algorithms are also studied. Computational experiments
on a shared memory multiprocessor vector computer are presented.
Key words.
asynchronous methods, two-stage iterative methods, linear systems,
multisplittings, parallel algorithms.
AMS(MOS) subject classifications.
65F10, 65F15.
Files.
vol.3.1995/pp24-38.dir/pp24-38.ps.
Forward References.
39. On graded QR decompositions of products of matrices. G. W. Stewart.
Abstract.
This paper is concerned with the singular values and vectors of a
product $M_{m}=A_{1}A_{2}\cdots A_{m}$ of matrices of order $n$. The
chief difficulty with computing them directly from $M_{m}$ is
that with increasing $m$ the ratio of the small to the large singular
values of $M_{m}$ may fall below the rounding unit, so that the former
are computed inaccurately. The solution proposed here is to compute
recursively the factorization $M_{m} = QRP^T$, where $Q$ is orthogonal,
$R$ is a graded upper triangular, and $P^T$ is a permutation.
Key words.
QR decomposition, singular value decomposition, graded matrix, matrix
product.
AMS(MOS) subject classification.
65F30.
Files.
vol.3.1995/pp39-49.dir/pp39-49.ps.
Forward References.
***********************************************
The contents of the June, 1995 issue of ETNA are
Electronic Transactions on Numerical Analysis
Volume 3, 1995
50. Adaptive k-Step Iterative Methods for Nonsymmetric Systems of
Linear Equations. Thomas A. Manteuffel, Gerhard Starke, and
Richard S. Varga.
Abstract.
This study is concerned with k-step methods for the iterative solution
of nonsymmetric systems of real linear equations. These are
generalizations of the Chebyshev (2-step) iteration, with the potential
for faster convergence in cases where the spectrum of the underlying
coefficient matrix is not approximated well by an ellipse. We
investigate the problem of optimizing the associated (asymptotic)
convergence factor with respect to a finite number of points (e.g.,
eigenvalue estimates obtained from using the Arnoldi process). We
formulate this minimization problem as an optimization problem with
constraints and propose an algorithm to compute near-best k-step
parameters. The computational advantages of the Chebyshev method,
such as avoidance of inner products, the implementation as an adaptive
method, and the simplicity of the overall scheme, carry over to the
case k > 2.
Key words.
k-step method, Chebyshev method, adaptive implementation, polynomial
iteration.
AMS(MOS) subject classification.
65F10.
Files.
vol.3.1995/pp50-63.dir/pp50-63.ps.
Forward References.
64. Minimal Gerschgorin Sets for Partitioned Matrices II. The Spectral
Conjecture. Alan Krautstengl and Richard S. Varga.
Abstract.
In an earlier paper from 1970, entitled "Minimal Gerschgorin sets for
partitioned matrices," a Spectral Conjecture, related to norms and
spectral radii of special partitioned matrices, was stated, this
conjecture being at the heart of the sharpness of the boundaries of the
associated minimal Gerschgorin sets under partitioning. In this paper,
this Spectral Conjecture is affirmatively settled, and is applied to the
sharpness of the minimal Gerschgorin set in the special case when the
block-diagonal entries are null matrices. The paper following this
article then makes use of the proof of the Spectral Conjecture to obtain
the general sharpness of the boundaries of the associated minimal
Gerschgorin sets for partitioned matrices.
Key words.
minimal Gerschgorin sets, partitioned matrices, monotonicity.
AMS(MOS) subject classification.
15A18.
Files.
vol.3.1995/pp64-80.dir/pp64-80.ps.
Forward References.
***********************************************
The contents of the September, 1995 issue of ETNA are
Electronic Transactions on Numerical Analysis
Volume 3, 1995
83. Minimal Gerschgorin sets for partitioned matrices III. Sharpness of
boundaries and monotonicity as a function of the partition. Richard S.
Varga and Alan Krautstengl.
Abstract.
Making use, from the preceding paper, of the affirmative solution of the
Spectral Conjecture, it is shown here that the general boundaries, of
the minimal Gerschgorin sets for partitioned matrices, are sharp, and
that monotonicity of these minimal Gerschgorin sets, as a function of
the partitionings, is obtained. These results extend and sharpen an
earlier paper from 1970 on this topic.
Key words.
minimal Gerschgorin sets, partitioned matrices, monotonicity.
AMS(MOS) subject classification.
15A18.
Files.
vol.3.1995/pp83-95.dir/pp83-95.ps.
Forward References.
96. Gaussian quadrature for matrix valued functions on the unit circle.
Ann Sinap.
Abstract.
The Gaussian quadrature formulas for matrix valued functions on the unit
circle are described. It is shown how the eigenvalues and eigenvectors
of a unitary lower block Hessenberg matrix can be used to compute an
approximation of a given matrix integral on the unit circle. A parallel
algorithm for this purpose has been implemented on a IBM SP1 and some
examples are worked out.
Key words.
orthogonal matrix polynomials, block Hessenberg matrices,
quadrature, parallel algorithm.
AMS(MOS) subject classification.
42C05, 41A55, 47A56, 65D32, 65Y05.
Files.
vol.3.1995/pp96-115.dir/pp96-115.ps.
Forward References.
***********************************************
The contents of the December, 1995 issue of ETNA are
Electronic Transactions on Numerical Analysis
Volume 3, 1995
116. On the correctness of some bisection-like parallel eigenvalue
algorithms in floating point arithmetic. James W. Demmel, Inderjit
Dhillon, and Huan Ren.
Abstract.
Bisection is a parallelizable method for finding the eigenvalues
of real symmetric tridiagonal matrices, or more generally symmetric
acyclic matrices. Ideally, one would like an implementation that was
simultaneously parallel, load balanced, devoid of communication, capable
of running on networks of heterogenous workstations, and of course
correct. But this is surprisingly difficult to achieve. The reason is
that bisection requires a function Count(x) which counts the number of
eigenvalues less than x. In exact arithmetic Count(x) is a monotonic
increasing function of x, and the logic of the algorithm depends on
this. However, monotonicity can fail, and incorrect eigenvalues may be
computed, because of roundoff or as a result of using networks of
heterogeneous parallel processors. We illustrate this problem, which
even arises in some serial algorithms like the EISPACK routine bisect,
and show several ways to fix it. One of these ways has been incorporated
into the ScaLAPACK library.
Key words.
symmetric eigenvalue problem, parallel algorithms, monotonicity,
correctness, floating point.
AMS(MOS) subject classification.
65F15, 65Y05.
Files.
vol.3.1995/pp116-149.dir/pp116-149.ps.
Forward References.
150. First-order system least squares for velocity-vorticity-pressure form
of the Stokes equations. Zhiqiang Cai, Thomas A. Manteuffel, and Stephen
F. McCormick.
Abstract.
In this paper, we study the least-squares method for the generalized
Stokes equations (including linear elasticity) based on the velocity-
vorticity-pressure formulation in d=2 or 3 dimensions. The least-squares
functional is defined in terms of the sum of the $L^2$- and $H^{-1}$-
norms of the residual equations, which is similar to that in [7], but
weighted appropriately by the Reynolds number (Poisson ratio). Our
approach for establishing ellipticity of the functional does not use
ADN theory, but is founded more on basic principles. We also analyze
the case where the $H^{-1}$-norm in the functional is replaced by a
discrete functional to make the computation feasible. We show that the
resulting algebraic equations can be preconditioned by well-known
techniques uniformly well in the Reynolds number (Poisson ratio).
Key words.
least squares, Stokes, elasticity.
AMS(MOS) subject classification.
65F10, 65F30.
Files.
vol.3.1995/pp150-159.dir/pp150-159.ps.
Forward References.
160. A parallel GMRES version for general sparse matrices. Jocelyne Erhel.
Abstract.
This paper describes the implementation of a parallel variant of GMRES on
Paragon. This variant builds an orthonormal Krylov basis in two steps: it
first computes a Newton basis then orthogonalises it. The first step
requires matrix-vector products with a general sparse unsymmetric matrix
and the second step is a QR factorisation of a rectangular matrix with
few long vectors. The algorithm has been implemented for a distributed
memory parallel computer. The distributed sparse matrix-vector product
avoids global communications thanks to the initial setup of the
communication pattern. The QR factorisation is distributed by using
Givens rotations which require only local communications. Results on an
Intel Paragon show the efficiency and the scalability of our algorithm.
Key words.
GMRES, parallelism, sparse matrix, Newton basis.
AMS(MOS) subject classification.
65F10, 65F25, 65F50.
Files.
vol.3.1995/pp160-176.dir/pp160-176.ps.
Forward References.
***********************************************
The contents of the March, 1996 issue of ETNA are
Electronic Transactions on Numerical Analysis
Volume 4, 1996
1. Non-stationary Parallel Multisplitting AOR Methods. Robert Fuster,
Violeta Migallon, and Jose Penades.
Abstract.
Non-stationary parallel multisplitting iterative methods based on
the AOR method are studied for the solution of nonsingular linear
systems. Convergence of the synchronous and asynchronous versions
of these methods is studied for $H$-matrices. Furthermore,
computational results about these methods on both shared and
distributed memory multiprocessors are discussed. The numerical
examples presented cover the non-stationary parallel multisplitting
Gauss-Seidel and SOR methods applied to the solution of the linear
system yielded by a finite difference discretization of the
two-dimensional Laplace's equation on a rectangular domain under
Dirichlet boundary conditions. These results show that non-stationary
AOR-type methods (synchronous and asynchronous) are better than the
corresponding standard parallel multisplitting AOR method. Moreover,
asynchronous versions always behave better than the synchronous ones.
Key words.
Non-stationary multisplitting methods, AOR method, asynchronous
algorithms, $H$-matrices, parallel implementation, shared memory,
distributed memory.
AMS(MOS) subject classification.
65F10.
Files.
vol.4.1996/pp1-13.dir/pp1-13.ps.
Forward References.
14. LMS-Newton Adaptive Filtering using FFT-based Conjugate Gradient
Iterations. Michael K. Ng and Robert J. Plemmons.
Abstract.
In this paper, we propose a new fast Fourier transform (FFT) based
LMS-Newton (LMSN) adaptive filter algorithm. At each adaptive time
step $t$, the $n$th-order filter coefficients are updated by using the
inverse of an $n$-by-$n$ Hermitian, positive definite, Toeplitz
operator $T(t)$. By applying the cyclic displacement formula for the
inverse of a Toeplitz operator, $T(t)^{-1}$ can be constructed using
the solution vector of the Toeplitz system $T(t)u(t) = e_n$, where
$e_n$ is the last unit vector. We apply the FFT-based
preconditioned conjugate gradient (PCG) method with the Toeplitz
matrix $T(t-1)$ as preconditioner to solve such systems at the step
$t$. As both matrix vector products $T(t) v$ and $T(t-1)^{-1} v$
can be computed by circular convolutions, FFTs are used throughout
the computations. Under certain practical assumptions in signal
processing applications, we prove that with probability 1 that the
condition number of the preconditioned matrix $T(t-1)^{-1}T(t)$ is
near to 1. The method converges very quickly, and the filter
coefficients can be updated in $O( n \log n)$ operations per adaptive
filter input. Preliminary numerical results are reported in order to
illustrate the effectiveness of the method.
Key words.
LMS-Newton adaptive filter algorithm, finite impulse response filter,
Toeplitz matrix, circulant matrix, preconditioned conjugate gradient
method, fast Fourier transform.
AMS(MOS) subject classifications.
65F10.
Files.
vol.4.1996/pp14-36.dir/pp14-36.ps.
Forward References.
37 A Note on the Accuracy of Symmetric Eigenreduction Algorithms.
K. Veselic.
Abstract.
We present some experimental results illustrating the fact that
on highly ill-conditioned Hermitian matrices the relative accuracy
of computed small eigenvalues by QR eigenreduction may drastically
depend on the initial permutation of the rows and columns. Mostly
there was an "accurate" permutation, but there does not seem to be
an easy method to get at it. For banded matrices, like those from
structural mechanics, the accurate pre-permutation, if it existed,
was mostly non-banded. This is particularly true of tridiagonal
matrices which shows that the tridiagonalization is not the only
factor responsible for the inaccuracy of the eigenvalues.
Key words.
LAPACK, QR method, Jacobi method, Hermitian matrices, eigenvalue
computation.
AMS(MOS) subject classification.
65F15.
Files.
vol.4.1996/pp37-45.dir/pp37-45.ps.
Forward References.
46 Matrix continued fractions related to first-order linear recurrence
systems. P. Levrie and A. Bultheel.
Abstract.
We introduce a matrix continued fraction associated with the first-order
linear recurrence system $Y_k = \theta_k Y_{k-1}$. A Pincherle type
convergence theorem is proved. We show that the $n$-th order linear
recurrence relation and previous generalizations of ordinary continued
fractions form a special case. We give an application for the numerical
computation of a non-dominant solution and discuss special cases where
$\theta_k$ is constant for all $k$ and the limiting case where
$\lim_{k \rightarrow +\infty} \theta_k$ is constant. Finally the notion
of adjoint fraction is introduced which generalizes the notion of the
adjoint of a recurrence relation of order $n$.
Key words.
recurrence systems, recurrence relations, matrix continued fractions,
non-dominant solutions.
AMS(MOS) subject classification.
40A15, 65Q05.
Files.
vol.4.1996/pp46-63.dir/pp46-63.ps.
Forward References.
64 A Note on Newbery's Algorithm for Discrete Least-Squares Approximation
By Trigonometric Polynomials. Heike Fassbender.
Abstract.
Recently fast, efficient and reliable algorithms for discrete
least-squares approximation of a real-valued function given at arbitrary
distinct nodes in $[0,2\pi)$ by trigonometric polynomials were presented
in different papers. These algorithms are based on schemes for the
solution of inverse unitary eigenproblems and require only O($mn$)
arithmetic operations as compared to O($mn^2$) operations needed for
algorithms that ignore the structure of the problem. In 1970 Newbery
already presented a O($mn$) algorithm for solving the discrete
least-squares approximation by trigonometric polynomials. In this paper
the connection between the different algorithms is illustrated.
Key words.
trigonometric approximation.
AMS(MOS) subject classification.
65D10, 42A10, 65F99.
Files.
vol.4.1996/pp64-74.dir/pp64-74.ps.
Forward References.
75 A Preconditioner for the Mortar Finite Element Method.
Mario A. Casarin and Olof B. Widlund.
Abstract.
Mortar elements form a family of nonconforming finite element methods
that are more flexible than conforming finite elements and are known to
be as accurate as their conforming counterparts. A fast iterative method
is developed for linear, second order elliptic equations in the plane.
Our algorithm is modeled on a hierarchical basis preconditioner
previously analyzed and tested, for the conforming case, by Barry
Smith and the second author. A complete analysis and results of
numerical experiments are given for lower order mortar elements and
geometrically conforming decompositions of the region into subregions.
Key words.
domain decomposition, mortar finite element method, hierarchical
preconditioner.
AMS(MOS) subject classification.
65F30, 65N22, 65N30, 65N55.
Files.
vol.4.1996/pp75-88.dir/pp75-88.ps.
Forward References.
***********************************************
The contents of the September, 1996 issue of ETNA are
Electronic Transactions on Numerical Analysis
Volume 4, 1996
89 An analysis of the pole placement problem.
I. The single-input case.
Volker Mehrmann and Hongguo Xu.
Abstract.
For the solution of the single-input pole placement problem we derive
explicit expressions for the feedback gain matrix as well as the
eigenvector matrix of the closed-loop system. Based on these formulas
we study the conditioning of the pole-placement problem in terms of
perturbations in the data and show how the conditioning depends on the
condition number of the closed loop eigenvector matrix, which is a
similar to a generalized Cauchy matrix, the norm of the feedback vector
and the distance to uncontrollability.
Key words.
pole placement, condition number, perturbation theory, Jordan form,
explicit formulas, Cauchy matrix, stabilization, feedback gain,
distance to uncontrollability.
AMS(MOS) subject classification.
65F15, 65F35, 65G05, 93B05, 93B55.
Files.
vol.4.1996/pp89-105.dir/pp89-105.ps.
Forward References.
106 Ray sequences of Laurent-type rational functions.
I. E. Pritsker.
Abstract.
This paper is devoted to the study of the asymptotic zero distribution of
Laurent-type approximants under certain extremality conditions analogous
to the condition of Grothmann, which can be traced back to Walsh's theory
of exact harmonic majorants. We also prove results on the convergence
of ray sequences of Laurent-type approximants to a function analytic
on the closure of a finitely connected Jordan domain and on the zero
distribution of optimal ray sequences. Some applications to the
convergence and zero distribution of the best $L_p$ approximants are
given. The arising theory is similar to Walsh's theory of maximally
convergent polynomials to a function in a simply connected domain.
Key words.
Laurent-type rational functions, zero distributions, convergence,
optimal ray sequences, best ${\rm L}_p$ approximants.
AMS(MOS) subject classification.
30E10, 30C15, 41A20, 31A15.
Files.
vol.4.1996/pp106-124.dir/pp106-124.ps.
Forward References.
125 On the solution of Cauchy systems of equations.
D. Calvetti and L. Reichel.
Abstract.
The development of fast solution methods for linear systems of equations
with a Cauchy matrix has recently received considerable attention. This
note presents new solution methods based on a modification of an
inversion formula described by Gastinel.
Key words.
fast algorithm, linear system, Cauchy matrix, Hankel matrix, Toeplitz
matrix.
AMS(MOS) subject classification.
65F10.
Files.
vol.4.1996/pp125-137.dir/pp125-137.ps.
Forward References.
***********************************************
=== EOF