Continuing invariant subspaces
If $A(s)$ is a parameter-dependent matrix, how do we compute an invariant subspace basis $V(s)$?
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
@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.
@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.
@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.
@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.
@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