Golub Memorial Conference - Abstracts and Transparency Files
James Baglama, URI
Block
Krylov Subspace Methods for Solving Large Sparse SVD and Eigenvalue Problems
Abstract: For the eigenvalue problem, we will describe the augmented block Householder Arnoldi method and for the SVD problem, we will describe the augmented block Lanczos bidiagonalization method. Both methods combine the advantages of a block routine with augmenting the Krylov subspace. These methods are fast, efficient, and reliable. Public domain MATLAB codes are available for both methods and several numerical experiments will be presented.
Tom Bella,
Quasiseparable
matrices and polynomials
Abstract: The interplay between polynomials and dense structured
matrices is a classical topic. Structure in this sense is interpreted
to mean their n2 entries can be
“compressed” to a smaller number O(n) of parameters. Operating directly on these parameters allows one
to design efficient fast algorithms
for these matrices and for the related applied problems.
In the past decades matrices with structures such as DFT/DCT/DST, Toeplitz,
Hankel, Vandermonde or Cauchy structure were the focus of attention. In this
talk, some results that demonstrate that a relatively new quasiseparable structure enables substantial generalizations of a number of different algorithms will be presented.
Adjoint
sensitivity analysis for two-layered shallow water model in a limited domain
Abstract: Sensitivity analysis
is
defined as the determination of the potential impact on some
quantitative measures of a forecast aspect due to arbitrary
perturbations
of the model dynamic fields at earlier times. Adjoints are
indispensible for
efficiently solving several types of optimization problems, which
includes
sensitivity analysis. Currently we are working on the development of
the adjoint tools for a spectral-element
based two-layered shallow water model in a limited domain with
non-reflecting
boundary conditions. This system has much in common with limited area
primitive
equation models used in numerical weather prediction.
Orthogonal
Polynomials, Moments, Measure Deformation, Dynamical Systems, and SVD Algorithm
1. Each of the Toda lattice and the Lotka-Volterra equation governs the evolution of a certain class of orthogonal polynomials whose orthogonality is determined by a specific time-dependent measure.
2. Since the measure deformation is explicitly known, moments can be calculated which, when properly assembled, lead to the conclusion abstractly, but literally, that the iterates of the QR algorithm and the SVD algorithm can be expressed in closed-form!
3. Hankel determinantal solutions are too complicated to be useful. However, a “smart” integrability-preserving discretization of the Lotka-Volterra equation can yield a new SVD algorithm.
(The fact that the SVD
algorithm is related to orthogonal polynomials, another subject of Gene’s
favorites, has surprised and pleased Gene in our last email communication a few
weeks before he passed away.)
Implementing the Retraction Algorithm for
factoring symmetric banded matrices
Abstract: Problems arising when
modeling structures subject to vibrations or in designing optical fibers
wrapped around a spool give rise to eigenvalue problems and linear systems
with symmetric, banded matrices. We present various variations of
the retraction algorithm which factors a matrix into a product of
matrices while preserving symmetry, the bandwidth, and element growth
even when the original matrix is indefinite. The factorization
may be used to solve a system or compute the inertia of a matrix. It
is based on the algorithm of Bunch and Kaufman, 1977, for symmetric nonbanded
systems, which grew out of the first paper that Gene Golub asked Linda Kaufman
to referee while she was his graduate student research assistant in 1973.
Theoretically the operation count is about 1/2 that of nonsymmetric banded
Gaussian elimination and 2/3 the space. Experimental results will be
presented comparing the various versions of the retraction algorithm with
LAPACK’s nonsymmetric band routines and the Snap-back code of Irony and
Misha Kilmer,
Multilevel Methods for Image Deblurring Problems (This presentation was cancelled due to illness)
Abstract: We present a multilevel method for discrete
ill-posed problems formulated
as least squares or total least squares problems. Our approach is meant to
preserve edges in the solution, a particularly important feature when applied to
signal or image deblurring problems. In this method we use the Haar wavelets as
restriction and prolongation operators. We show that the choice of the Haar
wavelet operator has the advantage of preserving matrix structure, such as
Toeplitz, among grids, and we discuss how this can be exploited to obtain
faster solvers on each level.
Steven Leon, UMass Dartmouth
Remembering Gene Golub, Part I - A Remarkable Career --- Part II - Serra House, the Golden Year, 1977 - 78
Abstract: The talk was presented in two parts. Part I was a brief overview of the career and accomplishments of Gene Golub. This presentation was made as part of the Opening Remarks for the conference. Part II consisted of remembrances of a very special year at Serra House. The presentation included photos, most of which were provided by Walter Gander. This presentation was part of the Remembrances given at the banquet honoring Gene.
.
.
Svante Littmarck (and Bjorn Sjodin), Comsol
Multiphysics SimulationsABSTRACT: The span of public domain solvers made available by the numerical linear algebra community helps tremendously when developing a software capable of solving general systems of coupled PDEs. The desire for more accurate mathematical models of real-world applications steadily poses new challenges corresponding to open research problems in solver technology and also new demands for integration with existing tools within CAD and other types of engineering software. We will talk about how publicly available solver technology is adapted to fit in a commercial software environment and also what challenges are met in the process.
Michael Neumann,
Optimization of the Spectral Radius of Sums and Products of Nonnegative Matrices
Abstract: Let A
be an n × n irreducible nonnegative
matrix. We will establish that over the set Ωn,n, of all n × n doubly stochastic matrices, the optimum values,
minimum and maximum, of the spectral radii of ρ(SA) and ρ(A + S), S in Ωn , occur at permutation matrices. For the case when A is also symmetric, a by–product of our
proof–technique yields a result allowing us to show that ρ(S1A) ≥ ρ(S2A) whenever S1
and S2 are two symmetric
matrices such that S1A and S2A and
nonnegative matrices and S1−
S2 is a positive
semidefinite matix. This result has several corollaries. One corollary is that ρ(S1A) ≥ ρ(S2A), when S1= (1/n)J and S2= (1/n − 1)(J − I), where J is the n × n matrix of
all ones. A second corollary is a comparison theorem for weak regular
splittings of two monotone matrices.
Our proof–techniques are strong enough to
show that if all the entries of A are
Vadim Olshevsky ,
Lipschitz
stability of canonical
Abstract: We study
Jordan-structure-preserving perturbations of matrices selfadjoint in the
indefinite inner product. The main result is Lipschitz stability of the
corresponding so-called similitude matrices. The result can be reformulated as
Lipschitz stability, under small perturbations, of canonical
Haesun Park, Georgia Institute of Technology ( joint work with Jingu Kim and Hyunsoo Kim)
Nonnegative Matrix Factorizations and Clustering (This presentation was cancelled due to a family emergency)
Variations of the
Nonnegative Matrix Factorization (NMF) are discussed for their
application to clustering. We show how interpreting the objective
function of K-means as that of a lower rank approximation with special
constraints allows comparisons between various formulations of NMF and
K-means and provides the insight to design new clustering algorithms.
We discuss introduction of additional constraints such as sparsity and
orthogonality on the factors in the NMF objective function for the
purpose of designing clustering algorithms based on NMF. The
experimental results with synthetic and text data shows that these
constrained NMF algorithms not only provide an alternative to K-means,
but rather give better and consistent solutions to clustering of
nonnegative data.
Bob Plemmons,
Least Squares with Nonnegativity Constraints
and Generalizations
Abstract: The work of Gene Golub on least squares computations has greatly influenced statistical applications throughout the mathematical sciences, as well as in engineering. In the past decade, work by Gene turned to computational, mathematical and statistical techniques for modeling and analyzing modern massive data sets, a promising and flourishing frontier in data and information systems and their applications. In this talk a survey of some of the algorithms for enforcing nonnegativity constraints in least squares computations is given. Generalizations involving approximate low-rank matrix and tensor factorizations are also discussed, and results from some numerical experiments on massive data sets are provided.
Daniel B Szyld,
Inexact Krylov Subspace Methods for PDEs and
Control Problems
Abstract: In many circumstances, a known
good preconditioner is not easily computable. Instead, an approximation
to it
is available. This is the case, for example, when the preconditioner
has an
inverse associated with it, such as in Schur complements (e.g., in
saddle point
problems), or in the reduced Hessian in some control problems. The
application of the preconditioner implies then an iterative solution of
a
linear system. In these cases, the question is how accurately to solve
the
(inner) iteration. In our work on Inexact Krylov methods, we have shown
that the inner iterations
can be solved progressively less accurately, as the underlying Krylov
method
(e.g, GMRES) converges to the overall solution. Computable inner
stopping
criteria have been developed to guarantee convergence of the overall
method. We
will discuss these criteria, and illustrate its application to several
problems. In particular, we will report on applying these ideas to
parabolic control
problems, where the reduced Hessian has two different inverses; and
thus two
inner iteration criteria are needed.
Homer Walker,
WPI and US Department of Energy
DIIS
Acceleration of Fixed-Point Iteration
Abstract: A certain fixed-point iteration is widely used in electronic
structure computations for determining electron densities having
minimum total energy. A certain auxiliary procedure, called Direct
Inversion on the Iterative Subspace (DIIS), is often used toaccelerate
its convergence. I will discuss DIIS as a general acceleration procedure for fixed-point iteration, focussing on a
linearly constrained least-squares problem occurring in DIIS and its
efficient solution through QR factorization updating.
Man-Chung Yeung
Abstract:
.
Pavel Zhlobich