StratiGraph and MCS Toolbox
StratiGraph is a Java-based tool for computing and displaying the stratification (closure hierarchy) of orbits or bundles of canonical structures. Matrix Canonical Structure (MCS) Toolbox is a Matlab toolbox for working with and computing canonical structure information.
The determination of the canonical form (Jordan, Kronecker, etc.) of a matrix or matrix pencil is an ill-posed problem in the presence of roundoff errors when the matrix or matrix pencil has multiple defective or derogatory eigenvalues. Therefore there exists modern numerical software based on staircase algorithms, such as GUPTRI, that regularizes these problems by allowing a tolerance for rank decisions to find their structure. However, the algorithms used are known to occasionally fail and thereby accidentally producing wrong, but nearby structures. Failure appears to occur when the matrix or matrix pencil is close to a manifold of interesting structures of higher codimension. Alan Edelman, Erik Elmroth, and Bo Kågström have proposed to make use of the mathematical knowledge of stratification of the obits or bundles of the canonical structures in order to enhance the staircase algorithm. This stratification, in effect, shows which structures are nearby other structures (in the sense of being in the closure) in the space of matrices. The stratification can be described as a connected graph, that grows exponentially with increasing matrix dimension. StratiGraph is a Java-based software tool that determines and visualizes such a graph.
Current version of StratiGraph supports stratification of:
- matrices under similarity,
- matrix pencils G-sH under strict equivalence,
- controllability pairs (A,B) under feedback equivalence,
- observability pairs (A,C) under injection equivalence,
- non-singular generalized state-space systems under feedback-injection equivalence, and
- linearizations of (full normal-rank) matrix polynomials.
Matrix Canonical Structure Toolbox
The Matrix Canonical Structure (MCS) Toolbox for Matlab includes a framework with data type objects for representing canonical structures and several routines for handling the interface to StratiGraph. Together with a plug-in to StratiGraph it is possible to import and export canonical structures between StratiGraph and Matlab.
Current version of MCS Toolbox supports canonical structures of:
- matrices (under similarity, congruence, and *congruence),
- matrix pencils (under strict equivalence, and symmetric and skew-symmetric pencils under congruence),
- matrix polynomials,
- system pencils (under feedback-injection equivalence).
Requires Java version 7 or later. For changes see the change log.
To run StratiGraph together with the MCS Toolbox, at least Matlab version 8.2 (R2013b) and the additional Java API matlabcontrol.jar are needed. See the readme file how to install and run.
For changes see the change log.
StratiGraph 3.0 (for Java version 7 or later)
Before you begin please read the Copyright information.
This gives a general introduction to StratiGraph and MCS toolbox, and a quick guide on how to use and install the software.
A user's guide on StratiGraph v2.2. No one is available for v3.x at present, but a brief introduction is presented in the book chapter [Kågström, Johansson, Johansson; 2012].
A user's manual for all functions and classes in the MCS toolbox.
References (a selection)
A. Dmytryshyn, S. Johansson, and B. Kågström.
Canonical structure transitions of system pencils. SIAM J. Matrix Anal. Appl., vol. 38(4), pp. 1249-1267, 2017.
Structure preserving stratification of skew-symmetric matrix polynomials. Linear Algebra Appl., vol. 532, pp. 266-286, 2017.
A. Dmytryshyn, V. Futorny, B. Kågström, L. Klimenko, and V. Sergeichuk. Change of the congruence canonical form of 2-by-2 and 3-by-3 matrices under perturbations and bundles of matrices under congruence. Linear Algebra Appl., vol. 469, pp. 305-334, 2015.
A. Dmytryshyn and B. Kågström. Orbit closure hierarchies of skew-symmetric matrix pencils. SIAM J. Matrix Anal. Appl., vol. 35(4), pp. 1429-1443, 2014.
S. Johansson, B. Kågström, and P. Van Dooren. Stratification of full rank polynomial matrices. Linear Algebra Appl., vol. 439, pp. 1062-1090, 2013.
E. Elmroth, S. Johansson, and B. Kågström. Stratification of controllability and observability pairs - Theory and use in applications. SIAM J. Matrix Anal. Appl., vol. 31(2), pp. 203-226, 2009.
A. Edelman, E. Elmroth, and B. Kågström. A geometric approach to perturbation theory of matrices and matrix pencils. Part II: A stratification-enhanced staircase algorithm. SIAM J. Matrix Anal. Appl., vol. 20(3), pp. 667-669, 1999.
A. Edelman, E. Elmroth, and B. Kågström. A geometric approach to perturbation theory of matrices and matrix pencils. Part I: Versal deformations. SIAM J. Matrix Anal. Appl., vol. 18(3), pp. 653-692, 1997.
B. Kågström, S. Johansson, and P. Johansson. StratiGraph Tool: Matrix Stratification in Control Applications. In L. Biegler, S. Campbell, and
V. Mehrmann, editors, Control and Optimization with Differential-Algebraic Constraints, ch. 5. SIAM Publications, 2012. (preprint)
A. Dmytryshyn, S. Johansson, B. Kågström, and P. Van Dooren.
Geometry of spaces for matrix polynomial Fiedler linearizationsTechnical report, UMINF 15.17, Department of
Computing Science, Umeå University, Sweden, 2015. (Submitted)
A. Dmytryshyn, S. Johansson, and B. Kågström. StratiGraph and the Matrix Canonical Structure ToolboxPoster, BIT Circus, Umeå, Sweden, 26-27 August, 2015.
A. Dmytryshyn, S. Johansson, and B. Kågström. Codimension computations of congruence orbits of matrices, symmetric and skew-symmetric matrix pencils using MatlabTechnical report, UMINF 13.18, Department of
Computing Science, Umeå University, Sweden, 2013.
S. Johansson. Reviewing the Closure Hierarchy of Orbits and Bundles of System Pencils and Their Canonical FormsTechnical report, UMINF 09.02, Department of Computing Science, Umeå University, Sweden, 2009.
A. Dmytryshyn. Tools for Structured Matrix Computations: Stratifications and Coupled Sylvester Equations. PhD Thesis, Umeå University, Sweden, December, 2015.
A. Dmytryshyn. Skew-Symmetric Matrix Pencils: Stratification Theory and Tools. Licentiate thesis, Umeå University, Sweden, February, 2014.
S. Johansson. Tools for Control System Design-Stratification of Matrix Pairs and Periodic Riccati Differential Equation Solvers. PhD thesis, Umeå University, Sweden, February, 2009.
P. Johansson. Software Tools for Matrix Canonical Computations and Web-based Software Library Environments. PhD thesis, Umeå University, Sweden, November, 2006.