SASCM

SASCM: Subspace acceleration Successive Constraint Method

SASCM is an implementation of the subspace accelerated Successive Constraint Method [1]. It solves a parameter dependent Hermitian eigenvalue problem

λ_min(A(μ)), μ in D

by sampling few smallest eigenpairs at carefully chosen sampling locations inside the parameter domain D. It collects the sampled eigenvectors into a subspace V that is used to compute accurate approximations to the smallest eigenvectors on the whole domain. The subspace upper bounds for \lambda_{min} are computed as smallest the smallest Ritz values inside V. For the lower bounds it combines the computed upper bounds (Ritz vectors) and the SCM lower bound [2] (computed by solving a LP) to compute more accurate subspace lower bounds. For a detailed algorithmic description, we refer to publication [1] or thesis [2].

It makes use of the MOSEK Matlab Toolbox 7 [4], which has to be installed and added to your Matlab path first.

SASCM is licensed under a 2-clause BSD license, see LICENSE.txt. Feel free to use it for your own projects. If you do so, please cite the corresponding publication [1] or thesis [2].

Installation

Download the code here: SASCM.zip

This code is research code and not intended for production use. If you publish a research paper using this code, we would appreciate a reference to the paper [1] describing our implementation.

After having downloaded and installed the Mosek optimization toolbox 7.1 [4], navigate to the SASCM folder. It is necessary to add the path to Mosek installation (to the right Matlab version) to the Matlab path. For example:

cd ~/mosek/7/toolbox/r2012a; addpath(pwd);

SASCM was sucessfully tested on

• Linux: R2012a

Earlier or later versions may not work.

Examples

Example codes for SASCM have filenames which start with "test-". Some examples are taken from [5].

The simplest random example is in the function test_SCM.m. A sample call is:

test_SCM(1000,1000,4,2,1);

which solves par-dep. Herm. eig. problem with 4 1000x1000 random Hermitian matrices, with 1000 elements in the training set and uses the subspace-acceleration.

Solution of linear program/alternatives to MOSEK

The code makes use of vertex identification feature inside the MOSEK toolbox, which ensures that the optimal point will (almost) always be a vertex of the convex polyhedron with exactly n active constraints. You can use other software packages instead, but for the toolbox to work accurately and efficiently it is essential to be able accurately identify exactly n the active constraints at the optimal point.

References

1. P.Sirkovic, D. Kressner: Subspace acceleration to parameter-dependent hermitian eigenproblems. SIAM J Matrix Anal. Appl. 37(2): 695--718, 2016.
2. P.Sirkovic: Low-rank methods for parameter-dependent eigenvalue problems and matrix equations. Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland, 2016.
3. D. B. P. Huynh, G. Rozza, S. Sen, and A. T. Patera.: A successive constraint linear optimization method for lower bounds of parametric coercivity and inf-sup stability constants. C. R. Math. Acad. Sci. Paris, 345(8):473--478, 2007.
4. MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 7.1 (Revision 28)., 2015.
5. D. B. P. Huynh, N. C. Nguyen, A. T. Patera, and G. Rozza: rbMIT software Software. MIT, Cambridge, US, 2010.

Author & Contact

Questions and suggestions about SASCM should be sent to Petar Sirkovic (other) or Daniel Kressner.

Disclaimer

The toolbox is published under the BSD 2-clause license. Note the following disclaimer:

This software is provided by the author ``as is'' and any express or implied warranties, including, but not limited to, the implied warranties of merchantability and fitness for a particular purpose are disclaimed. In no event shall the author or contributors be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage.