STANFORD UNIVERSITY -- SCCM SEMINARS
SCIENTIFIC COMPUTING AND COMPUTATIONAL MATHEMATICS
CS 531 (1 unit)
Numerical Analysis / Scientific Computing Seminar
Spring 2003
Gates B12, 16:15 - 17:30
List of Speakers (click for more details)
Detailed list
| Date | Speaker | Title & Abstract |
| Monday, April 7th |
Joe Grcar Lawrence Berkeley National Laboratory Email: jfgrcar@lbl.gov |
TITLE: Optimal Sensitivity Analysis of Linear Least Squares The linear least squares problem's sensitivities to perturbations are analyzed
based on the first-order sensitivities of metric projections to perturbations of
their sets. The latter is is a topic in real analysis and optimization theory that
underlies the kind of perturbation theory used in numerical analysis. The general
theory is applied to the linear least squares problem to obtain the following
results. Simple formulas are derived that asymptotically equal the size of the
minimal (in the Frobenius norm) backward errors. It is shown that such formulas
can be used to evaluate condition numbers. For full rank problems, Frobenius norm
condition numbers are determined exactly, and spectral condition numbers are
determined within a factor of two. Necessary and sufficient criteria for well
conditioning are established. A source of ill conditioning is found that explains
the failure of simple iterative refinement for these problems. Some error bounds,
including the one that LAPACK recommends, are found to unnecessarily overestimate
the error. Finally, several open questions are described. |
|
Friday, April 11th 3:15 - 4:30 PM Packard 202 |
Christoph L. Fabianek Vienna University of Technology Email: fabianek@cs.utk.edu Web: http://fsmat.at/~cfabiane |
TITLE: Functional Electrical Stimulation Electrical nerve and muscle stimulation is used to overcome bad, missing or lost body functions. In a research project at the Vienna General Hospital functional electrical stimulation of denervated skeletal muscles is studied. The aim is to allow paralyzed people to partially regain abilities like standing up or walking. In this talk I will give an introduction to functional electrical stimulation and discuss some of the mathematical problems arising in this field. Additionally current implementations and applications are presented. |
| Monday, April 21st |
Orly Alter Department of Genetics, Stanford Email: orly@genome.stanford.edu Web: http://www.stanford.edu/~orly See also: http://genome-www.stanford.edu/SVD & http://genome-www.stanford.edu/GSVD |
TITLE: SVD and GSVD for Modeling Genome-Scale mRNA Expression Data DNA microarray genome-wide expression data promise to enhance fundamental understanding of life on the molecular level, and may prove useful in medical diagnosis, treatment and drug design. Analysis of these new data requires mathematical tools that use large quantities of data and reduce the complexity of the data to make them comprehensible. These tools should enable normalization and classification of the expression data, as well as the incorporation of additional data into the analysis. These tools should also provide predictive models, i.e., mathematical frameworks for the description of the data, in which the mathematical variables and operations may be assigned biological meaning. Such models will facilitate the unraveling of the cellular machineries that generate, sense and react to the expression signal. I will start with a description of the use of singular value decomposition (SVD) to construct the first model for genome-wide expression data. The mathematical variables of SVD, the "eigengenes" and "eigenarrays," may be associated with independent processes and cellular states (such as observed genome-wide effects of regulators and measured samples in which these regulators are overactive), respectively. Mathematical filtering out of eigengenes and eigenarrays may simulate the experimental suppression of the cellular processes and states that these eigengenes and eigenarrays represent. I will illustrate this SVD model with analyses of time series and tumor sample data. I will then describe the use of generalized SVD (GSVD) to construct the first comparative model for two genome-scale expression datasets. The mathematical variables of GSVD, the "genelets" and "arraylets," may be associated with the effects of biological processes and experimental artifacts common to both datasets, as well as these that are exclusive to one dataset or the other. Mathematical reconstruction of gene expression in a subset of genelets may simulate experimental observation of only the process that these genelets represent. I will illustrate this model with a comparison of yeast and human cell cycle expression datasets, and in a comparison of mRNA expression and DNA copy number of tumor samples. I will conclude with a discussion of the insights that these models may offer into the biology, chemistry and physics of gene expression. |
| Wednesday, April 23rd |
Raghu Raghavan Image-Guided Neurologics, Baltimore, MD Email: raghu@radicus.net |
TITLE: Direct infusion in brain tissue: from start to finish Intra-parenchymal injection and transport of drugs and other agents have been studied both theoretically and experimentally. We report on a new systems approach, a combination of modeling and monitoring which we propose to increase the efficacy of such deliveries. We present our systems approach, how the computations support the system, the methods and results of the simulation, and comparisons with experiment. The talk is divided into three parts. In the first, we discuss the phenomena that occur, and how to exploit them for increased efficacy, and how to observe them via magnetic resonance imaging (MRI). When molecules are directly injected into the brain, the phenomena we must account for include: (i) backflow that creates a small fluid-filled cavity along part of the length of the needle or catheter; (ii) flow of fluid into the porous medium which is brain tissue; (iii) flow in a poroelastic medium, where the expansion of extracellular space due to the elasticity of brain tissue is taken into account; and (iv) agent transport, where the molecule in question is carried by the fluid flow, diffuses, leaks into capillaries, is metabolized, and so on. In the second part, we discuss how we solve the equations that account for the phenomena, and how we may obtain the input parameters needed for the calculation, again principally from MRI. Some new results are: the computation is driven by patient-specific magnetic resonance imaging data (only, i.e. no prior atlas, statistical or otherwise is needed although of course such can be used) and a stochastic particle method is used for all the partial difference equations. The particle method has the virtues that the simulation results are available as "real time" as one wants (at the expense of accuracy), no segmentation of brain structures is required (as one would need for finite element methods), the "weak solution" is automatically obtained and increasing knowledge of the chemical kinetics is easily incorporated. Further, the "roughness" of Brownian motion is actually an advantage, and all modern chips provide true random numbers on call. Finally, we review the status of the experimental data in checking the predictions. Experiments have been conducted in gels and pigs, and data on humans has been analyzed. The results on the few experiments so far, are extremely good. |
|
Friday, April 25th
3:15 - 4:00 TCSEQ 102 (across the street from Gates bldg.) |
James Lambers Stanford University - SCCM Email: lambers@sccm.Stanford.edu |
TITLE: Krylov Subspace Methods for Variable-Coefficient Initial-Boundary Value Problems The design and analyis of numerical methods for the solution of partial differential equations of the form du/dt + Lu = 0, where the differential operator L has constant coefficients, is greatly simplified by the fact that, for many methods, a closed-form representation of the computed solution as a function of (x,t) is readily available. This is due in large part to the fact that for such methods, the matrix that represents a discretization of L is diagonalizable, and the eigenvalues and eigenfunctions of this matrix are known. For variable-coefficient problems, however, this simplification is not available. This talk describes an alternative approach to the solution of this problem in the variable-coefficient case that leads to a new numerical method, called a Krylov subspace method, for which the computed solution can easily be represented as a function of (x,t), as in the constant-coefficient case. This function can be analytically differentiated with respect to time, resulting in new approaches to deferred correction and the solution of PDE that are second-order in time such as the telegraph equation. The basic idea behind the Krylov subspace method to use Gaussian quadrature in the spectral domain to compute components of the solution, rather than in the spatial domain as in spectral methods. For each component, a different approximation of the solution operator by a restriction to a low-dimensional Krylov subspace is employed, and each approximation is optimal in some sense for computing the corresponding component. As the Krylov subspace method is more effective for problems where the operator L has smooth coefficients, approaches to preconditioning differential operators using unitary similarity transformations are presented. These preconditioning techniques are based on the use of the uncertainty principle by Fefferman to obtain approximate diagonalizations of self-adjoint differential operators. |
| Monday, May 5th |
Thomas Strohmer Math Department - UC Davis |
Weyl-Heisenberg systems, uncertainty principles, and wireless communications I will show how recent methods from applied harmonic analysis can play a key role in modern wireless communications. I will first briefly describe Orthogonal Frequency Division Multiplexing (OFDM), which is one of the most promising transmission schemes for wireless communications. An important problem in OFDM is the design of transmission pulses that are robust against interference caused by time-varying channels. By exploiting the connection between Weyl-Heisenberg systems (a family of functions that consists of translations and modulations of some ``nice'' function), Banach algebras and OFDM I will construct a theoretical framework for the construction of orthogonal transmission functions that are optimally localized in the phase space. This localization property is crucial in order to mitigate the distortions caused by time-frequency dispersive channels. Some nice properties of Weyl-Heisenberg systems enable us to compute the aforementioned optimal pulses by a fast numerical algorithm, which is suitable for real-time applications. I will derive convergence rates for this algorithm and discuss some open problems. The proposed algorithm, which takes into account various practical constraints, has been recently used in the design of a modem for short-radio wave communications. |
| Wednesday, May 7th |
Daniele Bertaccini Universita' di Roma - Matematica Email: bertaccini@mat.uniroma1.it Web: http://www.mat.uniroma1.it/~bertaccini/ |
TITLE: Preconditioned iterative algorithms for time-dependent equations and shifted linear systems In this talk we will review some results on preconditioned iterative algorithms for differential equations. In particular, we will focus on our recent preconditioners for the solution of the nonsymmetric linear systems occurring in the numerical integration of time-dependent boundary value problems by means of linear multistep formulas in boundary value form which are based on block circulant-like approximations and on preconditioners for shifted linear system. |
| Friday, May 9th |
David E. Keyes Departments of Mathematics & Statistics and Computer Science Old Dominion University & Institute for Scientific Computing Research Lawrence Livermore National Laboratory Email: keyes@cs.odu.edu Web: http://www.math.odu.edu/~keyes |
TITLE: Scalable Solvers and Software for PDE Applications in DOE's SciDAC Like the theoretical peak performance of a computer system, theoretical efficiency for algorithms is rarely closely approached for real applications. While the quest for the "textbook efficiency" continues on many fronts, real users need to have their solver capabilities upgraded today to exploit the platform potential to run more highly resolved computations. The Terascale Optimal PDE Simulations (TOPS) project of the SciDAC initiative is working on both fronts --- attempting to make fundamental advances in numerical algorithms that will be integrated into tomorrow's scalable solver software while attempting to be of service to SciDAC application developers and others at the outset of the initiative. In this talk, we dwell on some practical aspects of migrating from a legacy (usually operator-split) nonlinear solver for evolutionary or equilibrium systems of PDEs to a Jacobian-free Newton-Krylov framework that provides strong controls on splitting error while still incorporating physically-based operator-split methodology (and even legacy subroutines) where possible. It is emphasized that to support even a single application from development through production use on various platforms, contemporary solver libraries must offer a menu of flexibly combinable and tunable components to allow application-specific and architecture-specific trade-offs (e.g., memory versus flops, synchronization frequency versus stability, robustness versus efficiency). We also discuss some experiences with the M3D extended magnetohydrodynamics code of our PPPL-based SciDAC partners, which is designed to underscore the desirability of being able to draw from a broad family of solvers within a single application. This talk is partially based on a new review article of Jacobian-Free Newton-Krylov methods co-authored with Dana Knoll of Los Alamos (available as the first link under "papers.html" at the speaker's website below). |
| Monday, May 12thth |
Zhaojun Bai
CS department - UC Davis |
Model Reduction of Nonlinear Dynamical Systems ``Reduced-order modeling of nonlinear systems is ultimate important and hard''. Means of applying Krylov subspace techniques for adaptively extracting accurate reduced-order models of large scale nonlinear dynamical systems is a relatively open problem. There has been much current interest in developing such techniques. We focus on a bilinearization method, which extends Krylov subspace techniques for linear systems. In this approach, a nonlinear system is first approximated by a bilinear system through Carleman bilinearization. Then a reduced-order bilinear system is constructed in such a way that it matches multimoments of transfer functions corresponding to the kernels of the Volterra-Wiener representation of the bilinear system. We will also show that the two-sided Krylov subspace technique matches significant more number of multimoments than the corresponding one-side technique. This is a joint work with Daniel Skoogh at Division of System Technology Department of Autonomous Systems, Swedish Defense Research Agency. |
| Wednesday, May 21st (MOVED) |
Gregory Boutry Math Department, University of Lille 1 (Visiting SCCM - Stanford) |
TITLE: Non-Square Pencils and Related Applications in Control Theory This talk is divided into two parts. The first part focuses on non-square matrix pencils (A-xB) where A and B are non-square with more rows than columns. Traditional methods for solving such non-square generalized eigenvalue problems (A-xB)v=0 are expected to lead to non-generic results in most cases. In this talk we propose a different treatment and search for the minimal perturbation on the original matrix pair such that eigenvalue/vector solutions are indeed possible. We present a new algorithm for the factorization of the pencil and some relation with the pseudospectra of rectangular matrix pencils. The second part focuses on the pair [A,B] of a dynamical systems in linear system theory and discusses system's controlability. We present some results on the minimal perturbation on the pair [A,B] to the nearest uncontrollable system, following the tools discussed earlier. |
| Monday, May 19th |
Jim Bunch Department of Mathematics University of California, San Diego La Jolla, CA 92093-0112 |
Applying Numerical Linear Algebra Techniques to Signal Processing Techniques have been developed in numerical linear algebra for distinguishing between infinite precision effects and finite precision effects. Although the structure of algorithms in signal processing prevents the direct application of typical numerical linear algebra techniques of analysis, much can be gained by adapting to signal processing some of those used in numerical linear algebra. A conceptual framework is presented that focusses on the distinction between a perturbation analysis of a problem and the stability analysis of an algorithm. Numerical analysis techniques for signal processing algorithms are discussed and terminology for a conceptual framework is suggested for distinguishing between errors propagated by the nature of the problem and errors propagated through the use of finite precision arithmetic. These techniques are applied to the Fast Transversal Filter algorithm, an algorithm that has long been known to diverge explosively, yet has nonetheless received much interest concerning the reasons behind its catastrophic divergence. |
|
Monday, June 2nd 16:30 - 17:30 |
Haesun Park Computer Science Department - University of Minnesota |
Linear discriminant analysis
based on the generalized singular value decomposition
and its applications Linear discriminant analysis (LDA) has been used for decades to extract features that preserve class separability. It is classically defined as an optimization problem involving covariance matrices that represent the scatter within and between clusters. The requirement that one of these matrices be nonsingular prevents its application to data sets in which the dimension of the data is higher than the number of data samples. This under-sampled data commonly occurs in many important applications including text processing and facial recognition. We show how the applicability of LDA can be extended by using the generalized singular value decomposition (GSVD) to circumvent the nonsingularity requirement. Alternatively, many recent studies have taken a two-stage approach in which the goal of the first stage is to reduce the dimension of the data enough so that it can be followed by classical LDA. The use of either principal component analysis (PCA) or latent semantic indexing (LSI) in the first stage is justified, by establishing the equivalence to the single-stage LDA/GSVD method. A computationally simpler choice for the first stage is also presented. Experimental results from support vector classification on document data and facial recognition illustrate higher efficiency and effectiveness achieved from dimension reduction by the LDA/GSVD. |