Shooting Methods for Locating Grazing
Phenomena in Hybrid Systems
Vaibhav Donde
Lawrence Berkeley National Laboratory
Hybrid systems are typified by strong coupling between
continuous dynamics and discrete events. For such piecewise smooth
systems, event triggering generally has a significant influence over
subsequent system behavior. Therefore it is important to identify
situations where a small change in parameter values alters the event
triggering pattern. The bounding case, which separates regions of
(generally) quite different dynamic behavior, is referred to as
grazing. At a grazing point, the system trajectory makes tangential
contact with an event triggering hypersurface. This poster will
present a framework for formulating conditions governing grazing
points, and numerically computing them. Both transient and periodic
behaviors are considered. The resulting boundary value problems
are solved using shooting methods that are applicable for general
nonlinear hybrid (piecewise smooth) dynamical systems. The grazing
point formulation underlies the development of a continuation
process for exploring parametric dependence. It also provides the
basis for an optimization technique that finds the smallest parameter
change necessary to induce grazing. Illustrative examples are drawn
from power systems, power electronics, and robotics, all of which
involve intrinsic interactions between continuous dynamics and
discrete events.
Simulating Intercellular Calcium
Signaling in Systems of Epithelial Cells Using Multiblock Grids
Petri Fast
Lawrence Livermore National Laboratory
Temporal and spatial calcium ion (Ca2+) mobilization
patterns play a key role in the regulation of cellular
function. We model the dynamics of calcium mediated by inositol
1,4,5-trisphosphate (IP3) in connected epithelial cells with a system
reaction-diusion equations on three dimensional structured multiblock
grids. We present a new computational framework that allows for
the first time the fully three dimensional modeling of intercellular
dynamics of calcium, IP3 and calcium buering species. We model
the intercellular connections between epithelial cells using a
geometrically realistic computational mesh with a simple continuum
description of gap-junctions permeable to IP3. Practical grid
generation techniques are discussed for cuboidal epithelial cells
consisting of a single layer of three dimensional coupled prismatic
domains each with an arbitrary polygonal top (apical) surfaces. A
novel numerical scheme is presented for diusion equations on
structured multiblock grids with gap-junction boundary conditions
du/dn = [u], where the normal ux across a membrane separating two
cells is proportional to a jump in the local concentration. We
present results illustrating the biological phenomena accessible
to simulations using our new numerical scheme.
Fast Parallel PageRank: A Linear
System Approach
David Gleich
Stanford University
In this paper we investigate the convergence of
iterative stationary and Krylov subspace methods for the
PageRank linear system, including the convergence dependency
on teleportation. We demonstrate that linear system iterations
converge faster than the simple power method and are less
sensitive to the changes in teleportation. In order to perform
this study we developed a framework for parallel PageRank
computing. We describe the details of the parallel implementation
and provide experimental results obtained on a 70-node Beowulf
cluster.
DISCERN: DIStributed Camera Event
Recognition Network
Teresa Ko
Sandia National Laboratories
The coupling of computer vision and wireless sensor network technology
enhances the future generations of monitoring systems. For acquiring
cutting edge speed and robustness, computer vision research needs to
take advantage of distributed dense information from different
viewpoints. To realize the full potential of wireless sensor networks,
there needs to be a method of capturing the information provided in
images when they can not be transported back to the base station for
centralized analysis due to bandwidth or power limitations. We
demonstrate a prototype system which illustrates in situ reasoning on
distributed sensor nodes from embedded image sensors.
Combining Direct and Iterative
Methods to Solve Partitioned Linear Systems
Felix Kwok
Stanford University
We examine two ways in which a singly bordered block
diagonal form (SBBDF) can be used for combining direct and iterative
methods to solve large sparse unsymmetric equations. Systems in SBBDF
arise naturally in domain decomposition methods, as well as after
some preprocessing by a coloring algorithm. In both cases, a direct
method is used to partially factorize local rectangular systems,
giving rise to square diagonal blocks and a doubly bordered block
matrix. The first method generates a Schur complement matrix and
an iterative method is used to solve this subsystem. The other uses
the factorizations to provide a modified block Jacobi preconditioner
for an iterative scheme on the whole system. To enhance convergence,
the square diagonal blocks are chosen so that they are as dominant
as possible using an unsymmetric permutation and scaling discussed
in Duff and Koster (2001).
This is joint work with
Iain Duff (RAL and CERFACS), Gene Golub (Stanford), and
Jennifer Scott (RAL).
Optimal Mode Selection for
Substructuring Method
Ben-Shan Liao
University of California at Davis
Substructure coupling methods, or component mode synthesis (CMS) methods,
have been studied in structural dynamics analysis since 1960s. Recently an
automated multilevel substructuring (AMLS) method has been proposed for
extremely large systems. In these substructure-based methods, the modes of
subsystems associated with the lowest frequencies are typically retained.
This mode selection rule is largely heuristic. In this paper, we use
moment-matching
analysis to derive a new mode selection criterion, which is compatible to
the
one recently derived in the optimal modal reduction (OMR) method using
Dirichlet-to-Neumann (DtN) mapping. The improvements of the new mode
selection
criterion are demonstrated by numerical examples from structural dynamics
in both time-domain and frequency domain.
Relative Periodic Solutions
of the Complex Ginzburg-Landau Equation
Vanessa L. Lopez
Lawrence Berkeley National Laboratory
The complex Ginzburg-Landau equation (CGLE) is a widely
studied partial differential equation with applications in many
areas of science, including fluid dynamics, superconductivity, and
chemical turbulence. As such, it has become a model problem for
the study of nonlinear evolution equations with chaotic dynamics.
One commonly used tool to understand such dynamical systems is
periodic orbit theory. For example, statistical averages that
provide a description of the asymptotic behavior of a chaotic
dynamical system can be approximated from the short-term dynamics
of the (unstable) periodic solutions on an attractor of the
chaotic system.
In this work, we report on a search for relative periodic
solutions to the one-dimensional CGLE with periodic boundary
conditions. We have found a large collection of relative periodic
solutions in a chaotic region of the CGLE, including new periodic
solutions with broad temporal and spatial spectra. These solutions
exhibit a wide variety of temporal dynamics and are all unstable.
In addition, preliminary results indicate that weighted averages
over the collection of relative periodic solutions accurately
approximate the value of several functionals on typical trajectories
in a chaotic region of the CGLE.
A Unifying Framework for Polynomial Zerofinders Applied
to Eigenvalue Computations
Aaron Melman
St. Mary's College
We start by considering the problem of computing the
smallest eigenvalue of a symmetric positive definite Toeplitz
matrix. Although, by itself, this problem may be of only
moderate interest, the development of methods to solve it have
led to interesting numerical analysis questions. We briefly touch
on some of those questions, and then concentrate on an unusual
way to construct polynomial zerofinders. More specifically, we
show a correspondence between several classical zerofinders and a
constrained optimization problem. Not only does this lead to new
methods, it also allows one to obtain overshooting properties for
any method that fits into this optimization framework. This is joint
work with W.B. Gragg at the naval Postgraduate School in Monterey, CA.
Perfect Algebraic Coarsening
Jonathan Edward Moussa
University of California at Berkeley
An approximate factorization scheme for sparse matrices
is considered whose error can be systematically reduced while
maintaining the sparsity of the matrix at intermediate steps. The
basic step of this method, which diagonalizes one row and column,
is a general "local" transformation rather than the rank-1 update
used in Gaussian elimination. Numerical tests of these local
transformations are performed on the Helmholtz equation on a uniform
2D grid.
Computing seismic waves using
embedded boundary methods
Stefan Nilsson
Lawrence Livermore National Laboratory
A new code modeling seismic events is being developed by
us. The code uses a high-order (4-space,4-time) method internally,
and degrades to second order close to boundaries. Boundary conditions
are satisfied using an embedded boundary technique, enabling accurate
modeling of topography and internal material discontinuities where
the jump conditions are explicitly satisfied. A cartesian grid is
utilized everywhere so grid generation is trivial.
An Iterative Method for Estimating
the Optimal Backward Errors of Linear Least Squares Problems
Zheng Su
Stanford University
An iterative approach is suggested and tested to evaluate
an estimate for the optimal (that is, the minimal Frobenius norm)
size of backward errors for least squares problems. It is compared
to other iterative approaches available in the literature.
Using Pattern Search Methods for
Surface Structure Determination
Zhengji Zhao
Lawrence Berkeley National Laboratory
The surface structure plays an important role in
determining the properties of a nanomaterial. Determining the
surface structure can be formulated as an inverse problem by
fitting simulated low-energy electron diffraction intensities to
experimental data. The solution of the inverse problem requires
both local and global optimizations. The problem has a number
of characteristics that make it difficult: there exist a lot of
local minima, it has both continuous and categorical variables,
the objective function is discontinuous or not defined, there are
no derivatives, and function evaluations are expensive. We have
adapted and applied the Generating Set Search (GSS) method for
solving this problem. We have found that GSS has produced better
results than previously used genetic algorithms, both in terms of
performance and locating the optimal results.