### 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

D. Bindel, M. Friedman, W. Govaerts, J. Hughes, and Y. A. Kuznetsov, “Numerical Computation of Bifurcations in Large Equilibrium Systems in MATLAB,” 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.

D. Bindel, J. Demmel, and M. Friedman, “Continuation of Invariant Subspaces in Large Bifurcation 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.

C. Bruyns-Maxwell and D. Bindel, “Modal Parameter Tracking for Shape Changing Objects,” in 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.

D. Bindel, “Structured and Parameter-Dependent Eigensolvers for Simulation-Based Design of Resonant MEMS,” PhD thesis, University of California, Berkeley, 2006. Appears as Tech Report EECS-2006-109.
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.

C. Bruyns and D. Bindel, “Shape Changing Symmetric Objects for Sound Synthesis,” in 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.

D. Bindel and J. Demmel, “Continuation of Invariant Subspaces for Large Bifurcation Problems,” UC Berkeley Computer Science Division, EECS-2006-13, Feb. 2006. Appeared in SIAM Journal on Scientific Computing in 2008.
@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.

D. Bindel, J. Demmel, W. Govaerts, and Y. Kuznetsov, “Bifurcation Analysis of Large Equilibrium Systems in MATLAB,” in 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
cisminisymposium external organizer

#### Inclusion Regions for Bifurcation Analysis

UC Berkeley LAPACK Seminar
cis eigenboundsseminar local

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

Householder Symposium
cismeeting external invited plenary

#### Parameter-Dependent Eigencomputations and MEMS Applications

UC Berkeley LAPACK seminar
cis mems rf-memsseminar local

#### Refining Approximate Invariant Subspaces

UC Berkeley LAPACK seminar
cisseminar local