### Summary

In many problems, we care about eigenvalues not just for a fixed
matrix, but for a parameterized family of matrices. For example, in a
numerical bifurcation analysis, one analyzes eigenvalues of Jacobian
matrices associated with behavior near a parameterized family of
dynamical equilibria. When an eigenvalue crosses over the imaginary
axis, a change of stability ensues. A natural idea for computation is
to use *continuation* to quickly recompute the eigenvalues closest to
the imaginary axis as we walk along a branch of dynamical equilibria.
But even for very smooth families of matrices, individual eigenvectors
can be ill-behaved or even discontinuous; so instead of looking
continuing individual eigenvectors, we may continue *invariant
subspaces*. Our work focuses on how to carry out this continuation
efficiently for the types of large, sparse problems that arise in PDE
stability analyses. We also care about deriving bounds that
ensure that our algorithms do not miss a bifurcation event because we
failed to compute a critical eigenvalue.

### Papers

*Journal of Computational and Applied Mathematics*, vol. 261, pp. 232–248, 2014.

@article{2014-matcont, author = {Bindel, David and Friedman, Mark and Govaerts, Willy and Hughes, Jeremy and Kuznetsov, Yuri A.}, title = {Numerical Computation of Bifurcations in Large Equilibrium Systems in {MATLAB}}, journal = {Journal of Computational and Applied Mathematics}, volume = {261}, pages = {232--248}, year = {2014}, doi = {10.1016/j.cam.2013.10.034} }

#### Abstract:

The Continuation of Invariant Subspaces (CIS) algorithm produces a
smoothly-varying basis for an invariant subspace R(s) of a
parameter-dependent matrix $A(s)$. We have incorporated the CIS
algorithm into `Cl_matcont`

, a Matlab package for the study of
dynamical systems and their bifurcations. Using subspace reduction, we
extend the functionality of `Cl_matcont`

to large-scale computations
of bifurcations of equilibria. In this paper, we describe the
algorithms and functionality of the resulting Matlab bifurcation
package `Cl_matcontL`

. The novel features include: new CIS-based,
continuous, well-scaled test functions for codimension 1 and 2
bifurcations; detailed description of locators for large problems; and
examples of bifurcation analysis in large sparse problems.

*SIAM Journal on Scientific Computing*, vol. 30, no. 2, pp. 637–656, Feb. 2008.

@article{2008-cis, author = {Bindel, David and Demmel, James and Friedman, Mark}, title = {Continuation of Invariant Subspaces in Large Bifurcation Problems}, journal = {SIAM Journal on Scientific Computing}, volume = {30}, number = {2}, pages = {637--656}, month = feb, year = {2008}, doi = {10.1137/060654219} }

#### Abstract:

We summarize an algorithm for computing a smooth orthonormal basis for an invariant subspace of a parameter-dependent matrix, and describe how to extend it for numerical bifurcation analysis. We adapt the continued subspace to track behavior relevant to bifurcations, and use projection methods to deal with large problems. To test our ideas, we have integrated our code into MATCONT, a program for numerical continuation and bifurcation analysis.

*Proceedings of DAFx 2007*, 2007.

@inproceedings{2007-sound, author = {Bruyns-Maxwell, Cynthia and Bindel, David}, title = {Modal Parameter Tracking for Shape Changing Objects}, booktitle = {Proceedings of DAFx 2007}, month = sep, year = {2007} }

#### Abstract:

For interactive sound synthesis, we would like to change the shape of a finite element model of an instrument and rapidly hear how the sound changes. Using modal synthesis methods, we would need to compute a new modal decomposition with each change in the geometry, making the analysis too slow for interactive use. However, by using modes computed for one geometry to estimate the frequencies for nearby geometries, we can hear much more quickly how changing the instrument shape changes the sound. In this paper, we describe how to estimate resonant frequencies of an instrument by combining information about the modes of two similar instruments. We also describe the balance between computational speed and accuracy of the computed resonances.

**2008 Householder Award (best NLA thesis over three years)**

@phdthesis{2006-dissertation, author = {Bindel, David}, title = {Structured and Parameter-Dependent Eigensolvers for Simulation-Based Design of Resonant {MEMS}}, school = {University of California, Berkeley}, month = aug, year = {2006}, status = {unrefereed}, submit = {Appears as Tech Report EECS-2006-109.}, notable = {2008 Householder Award (best NLA thesis over three years)} }

#### Abstract:

This dissertation is about computational tools to aid in the design of resonant Micro-Electro-Mechanical Systems (MEMS), tiny vibrating devices built by processes like those used to make integrated circuits. Vibrating MEMS are used in accelerometers and gyroscopes, in sensors to detect chemicals and to measure pressure, and in communication devices such as cell phones. MEMS engineers can use computer simulations to design devices using fewer costly and time-consuming prototype tests, but these simulations are only as useful as the models on which they are built. In this work, we contribute new mathematical models, numerical methods, and software tools to simulate resonant MEMS, and apply these tools to analyze specific devices. We describe physical models of damped vibrations of MEMS, including anchor loss and thermoelastic effects which are widely recognized as important, but not modeled in generality by existing tools. Though the resulting systems of equations are large and non-Hermitian, and depend nonlinearly on frequency, we use the equation structure to develop efficient structured Krylov subspace projection methods for computing free vibrations and reduced-order models. We also provide efficient continuation methods for re-computing eigendecompositions under changes to design parameters or operating conditions. Our models and analysis methods are integrated into HiQLab, a new finite element tool with a particularly flexible architecture which we have designed. Using HiQLab, we simulate example resonator designs, and compare our results to laboratory measurements. Our simulations reveal a previously-unknown mode interference phenomenon, subsequently observed in experiments, which dramatically affects the amount of damping near certain critical values of geometric parameters.

*Proceedings of 121st AES*, 2006.

@inproceedings{2006-sound, author = {Bruyns, Cynthia and Bindel, David}, title = {Shape Changing Symmetric Objects for Sound Synthesis}, booktitle = {Proceedings of 121st AES}, month = oct, year = {2006} }

#### Abstract:

In the last decade, many researchers have used modal synthesis for sound generation. Using a modal decomposition, one can convert a large system of coupled differential equations into simple, independent differential equations in one variable. To synthesize sound from the system, one solves these decoupled equations numerically, which is much more efficient than solving the original coupled system. For large systems, such as those obtained from finite-element analysis of a musical instrument, the initial modal decomposition is time-consuming. To design instruments from physical simulation, one would like to be able to compute modes in real-time, so that the geometry, and therefore spectrum, of an instrument can be changed interactively. In this paper, we describe how to quickly compute modes of instruments which have rotational symmetry in order to synthesize sounds of new instruments quickly enough for interactive instrument design.

@techreport{2006-cis, author = {Bindel, David and Demmel, James}, title = {Continuation of Invariant Subspaces for Large Bifurcation Problems}, number = {EECS-2006-13}, institution = {UC Berkeley Computer Science Division}, month = feb, year = {2006}, status = {unrefereed}, submit = {Appeared in SIAM Journal on Scientific Computing in 2008.} }

#### Abstract:

We summarize an algorithm for computing a smooth orthonormal basis for an invariant subspace of a parameter-dependent matrix, and describe how to extend it for numerical bifurcation analysis. We adapt the continued subspace to track behavior relevant to bifurcations, and use projection methods to deal with large problems. To test our ideas, we have integrated our code into MATCONT, a program for numerical continuation and bifurcation analysis.

*Proceedings of ICCS 2005*, 2005, vol. 3514, pp. 50–57.

@inproceedings{2005-iccs, author = {Bindel, David and Demmel, James and Govaerts, Willy and Kuznetsov, Yuri}, title = {Bifurcation Analysis of Large Equilibrium Systems in {MATLAB}}, booktitle = {Proceedings of ICCS 2005}, volume = {3514}, series = {Springer LNCS}, pages = {50--57}, month = apr, year = {2005}, doi = {10.1007/11428831_7} }

#### Abstract:

The Continuation of Invariant Subspaces (CIS) algorithm produces a
smoothly varying basis for an invariant subspace $R(s)$ of a
parameter-dependent matrix $A(s)$. In the case when $A(s)$ is the
Jacobian matrix for a system that comes from a spatial discretization
of a partial differential equation, it will typically be large and
sparse. `Cl_matcont`

is a user-friendly MATLAB package for the study
of dynamical systems and their bifurcations. We incorporate the CIS
algorithm into `Cl_matcont`

to extend its functionality to large scale
bifurcation computations via subspace reduction

### Talks

#### Continuation of Sparse Eigendecompositions

SIAM CSE

cis
•
minisymposium external organizer

#### Inclusion Regions for Bifurcation Analysis

UC Berkeley LAPACK Seminar

cis eigenbounds
•
seminar local

#### Continuation of Invariant Subspaces of Sparse Parameter-Dependent Matrices

Householder Symposium

cis
•
meeting external invited plenary

#### Parameter-Dependent Eigencomputations and MEMS Applications

UC Berkeley LAPACK seminar

cis mems rf-mems
•
seminar local

#### Refining Approximate Invariant Subspaces

UC Berkeley LAPACK seminar

cis
•
seminar local