Research project 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 computing and representing canonical structure information.
Funded by SSF, VR, eSSENCE och UMIT (EU Structural Fund Objective 2).
Alan Edelman (MIT, Massachusetts) and Paul Van Dooren (UCL, Belgium)
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 closure hierarchy graphs associated with orbit and bundle stratifications.
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.
The Matrix Canonical Structure (MCS) Toolbox for Matlab provides a framework with data type objects for representing canonical structures and computational functions related to canonical forms. 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).
The MCS toolbox includes routines for computing the canonical structure information using staircase algorithms. These are based on the GUPTRI (Generalized UPper TRIangular) algorithm [Demmel & Kågström, 1993] for matrix pencils. The GUPTRI form reveals the fine canonical structure information of a matrix pencil. For example, for a linearized model we can compute its canonical structure and then let StratiGraph determine and visualize nearby structures in the closure hierarchy.
StratiGraph 4.0 (2018-04-19)
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.
MCS Toolbox 0.7 (2019-09-13)
For changes see the change log.
For full functionallity with StratiGraph the interface files (download here) in the Matlab plugin for StratiGraph 4.0 must be updated. See included readme file.
StratiGraph 3.1 (2016-02-10)
StratiGraph 3.0 (for Java version 7 or later)
MCS Toolbox 0.6 (2018-04-19)
MCS Toolbox 0.5 (2016-02-10)
Any questions regarding the software should be send to
Stefan Johansson (email)
Department of Computing Science
Umeå University
StratiGraph - License
MCS Toolbox - License
Before you begin please read the Copyright information.
StratiGraph - Readme
MCS Toolbox - Readme
General introductions to StratiGraph and MCS toolbox, and quick guides on how to use and install the software.
StratiGraph v2.2 - User's guide
User's guide for StratiGraph v2.2 (partly outdated). None is available for v3 or higher at present, but a brief introduction to StratiGraph 3.0 is presented in the book chapter [Kågström, Johansson, Johansson; 2012].
MCS Toolbox - User's manual v0.7
User's manual for all functions and classes in the MCS toolbox. See also this presentation (presented at the 22nd Conference of the International Linear Algebra Society, 2019)
A selection of references.
A. Dmytryshyn, S. Johansson, B. Kågström, and P. Van Dooren. Geometry of Matrix Polynomial Spaces. Foundations of Computational Mathematics, 2019.
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.
A. Dmytryshyn. 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)
S. Johansson and B. Kågström. Matlab Tools for Computing Canonical Structure Information. Presentation, The 22nd Conference of the International Linear Algebra Society, Rio de Janeiro, Brazil, July 8-12, 2019.
A. Dmytryshyn, S. Johansson, and B. Kågström. StratiGraph and the Matrix Canonical Structure Toolbox. Poster, Housholder Symposium XX, Blacksburg, VA, USA, June 18-23, 2017.
A. Dmytryshyn, S. Johansson, and B. Kågström. Stratifications of structured matrix pencils. Part I: Skew-symmetric and symmetric cases. Presentation, The 19th Conference of the International Linear Algebra Society, Seoul, Korea, Aug 6-9, 2014.
A. Dmytryshyn, S. Johansson, and B. Kågström. Stratifications of Structured Matrix Pencils. Part II: Generalized State-Space Systems. Presentation, The 19th Conference of the International Linear Algebra Society, Seoul, Korea, Aug 6-9, 2014.
A. Dmytryshyn, S. Johansson, and B. Kågström. Codimension computations of congruence orbits of matrices, symmetric and skew-symmetric matrix pencils using Matlab. Technical 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 Forms. Technical 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.
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.
