StratiGraph
version 4.0
A Java-based tool for the computation and visualization of closure
hierarchy graphs of orbits and bundles of matrices, matrix pencils,
matrix polynomials, and various system pencils.
CONTENTS
- Introduction
- Installation
- The Matlab plugin
- Compatibility
- Known limitations and problems
- Contact
- Developers and collaborators
INTRODUCTION
The determination of the Jordan form of a matrix or the Kronecker form
of a 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 [GW76]. Therefore there exists modern
numerical software, such as GUPTRI [DK93] 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 pencil is
close to a manifold of interesting structures of higher
codimension. Alan Edelman, Erik Elmroth and Bo Kågström [EEK99] have
proposed to make use of the mathematical knowledge of stratification
of canonical structures (Jordan, Kronecker, etc.) 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 and therefore forms a closure
hierarchy graph.
The stratification can be described as a connected graph, that grows
exponentially with increasing matrix dimension. Nodes in the graph
represent orbits or bundles of the studied setup (matrix, matrix
pencil, etc.). An edge between two nodes in the graph represents a
covering relation in the closure hierarchy, i.e., one of the nodes
represents an orbit or a bundle in the closure of the other, and there
are no other orbits or bundles between the two in the closure
hierarchy. We present the graphs with the more generic structures at
the top and the more degenerate at the bottom.
Current version includes stratification of:
* Matrices under similarity.
* Matrix pencils G-sH under strict equivalence.
* System pencils under feedback-injection equivalence
[A B] [E 0]
[C D] - s [0 0], where E is non-singular,
corresponding to the state-space system
dx/dt = Ax(t) + Bu(t),
y = Cx(t) + Du(t),
and particular systems their of.
* Matrix polynomials P(s) on a corresponding Fiedler linearization
under strict equivalence.
Further examples and explanation of the theoretical background can be
found in [DJK17,DJKVD15,EEK99,EJK99,EJK09,JKVD13,KJJ12]. A detailed
description of the tool is found in the User's guide [J99] (written
for StratiGraph 2.x and therefore partly outdated) and in [KJJ12].
StratiGraph also includes build-in help.
StratiGraph version 1.0 was initially implemented within a Master
thesis project [J98] and has been further developed. See CHANGELOG.md
for a full description of all versions and changes.
INSTALLATION
Unpack and copy the folder/jar-file(s) to desired location. If
StratiGraph is to be used together with the Matrix Canonical Structure
(MCS) toolbox and Matlab, preferably save the jar-files in the root
folder of the MCS toolbox. Run StratiGraph, or from Matlab, call
sgopen to run StratiGraph (see also below).
THE MATLAB PLUGIN
The Matlab Plugin is distributed together with StratiGraph and
consists of the SG plugin jar-file 'sgplugin-matlab.jar' and the
folder 'sginterface/' with Matlab-files.
Copy the jar-file to the root path of the MCS toolbox. Copy the
'sginterface/' folder as a subfolder to the MCS toolbox and add it to
Matlab's search path.
The Matlab plugin uses the Java API 'matlabcontrol' to communicate
with Matlab. matlabcontrol can be downloaded from
http://code.google.com/p/matlabcontrol/
If StratiGraph and the SG plugin jar-files are not in the root folder
of the MCS toolbox, the jar-files must first be added to Matlab's Java
classpath with 'javaaddpath'. The same holds for the matlabcontrol
jar-file. If not done before starting StratiGraph, the jar-files are
automatically added and are assumed to be in the root path of the MCS
toolbox. For a permanent installation (optional), the jar-files may be
permanently added to the Java class path in Matlab.
To run StratiGraph together with the MCS toolbox, StratiGraph must be
opened within Matlab. Type at the Matlab prompt
> sgopen
Final step to get the connection between Matlab and StratiGraph to
work is to load the extensions Matlab Server Communicator and MCS
Toolbox Integrator in the Plugin Manager in StratiGraph. If this is
not done automatically during start-up, enable the plugins in the
Plugins Manager found under the Window menu.
COMPATIBILITY
StratiGraph version 4.0 requires Java Runtime Environment (JRE)
version 1.7 or later.
The Matlab plugin requires Matlab version 8.2 (R2013b) or later, MCS
Toolbox version 1.0 or later, and matlabcontrol version 4.1.0 or
later. (Should also work with matlabcontrol version 4.0.0, but this is
untested).
KNOWN LIMITATIONS AND PROBLEMS
The stratification of square full-normal rank polynomial matrices only
shows one of possible many stratification graphs.
StratiGraph cannot create a connection with an existing Matlab session
if started outside of Matlab. A consequence is when StratiGraph is
started outside of Matlab with the Matlab plugins enabled, Matlab will
be started but terminated directly afterward.
CONTACT
Bugs and questions can be submitted to:
Stefan Johansson, stefanj@cs.umu.se (project leader)
Bo Kågström, bokg@cs.umu.se (PI)
Department of Computing Science
Umeå University
SE - 901 87 Umeå, Sweden
DEVELOPERS AND COLLABORATORS
StratiGraph is developed at the Department of Computing Science,
Umeå University (Sweden) by the following people.
Programming: Stefan Johansson and Pedher Johansson.
Scientific contribution: Andrii Dmytryshyn, Erik Elmroth, Pedher Johansson,
Stefan Johansson, and Bo Kågström.
A Special thanks to our collaborators:
Alan Edelman (MIT, Massachusetts) and Paul Van Dooren (UCL, Belgium).
REFERENCES
[DK93] J. Demmel and B. Kågström.
The Generalized Schur Decomposition of an Arbitrary Pencil A - lambda B:
Robust Software with Error Bounds and Applications. Part I: Theory and
Algorithms and Part II: Software and Applications.
ACM Trans. Math. Software, Vol.19(2), pp.160-174, 175-201, June 1993.
[DJK17] 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.
[DJKVD15] A. Dmytryshyn, S. Johansson, B. Kågström, and P. Van Dooren.
Geometry of spaces for matrix polynomial Fiedler linearizations.
Report UMINF 15.17, Department of Computing Science,
Umeå University, Sweden, 2015. (Revised version submitted)
[EEK99] 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-699, 1999.
[EJK99] E. Elmroth, P. Johansson, and B. Kågström.
Computation and Presentation of Graphs Displaying Closure Hierarchies of
Jordan and Kronecker Structures.
Report UMINF 99.11, Department of Computing Science,
Umeå University, Sweden, 1999.
[EJK09] E. Elmroth, S. Johansson, and B. Kågström.
Stratification of Controllability and Observability Pairs - Theory and
Use in Applications.
SIAM J. Matrix Analysis and Applications, Vol. 31(2), pp.203-226, 2009.
[GW76] G. Golub and J. H. Wilkinsson.
Ill-conditioned eigensystems and the computation of the Jordan canonical
form. SIAM Review, Vol. 18(4), pp.578-619, 1976.
[J98] P. Johansson.
StratiGraph - En Java-baserad användaryta för beräkning och presentation av
grafer som beskriver hierarkier av Jordan och Kroneckerstrukturer.
Master Thesis, UMNAD 214.98, Department of Computing Science,
Umeå University, Sweden, 1998.
[J99] P. Johansson.
StratiGraph User's Guide version 2.0.
Report UMINF 03.21, Department of Computing Science,
Umeå University, Sweden, 1999.
[JKVD13] S. Johansson, B. Kågström, and P. Van Dooren.
Stratification of full rank polynomial matrices.
Linear Algebra and its Applications, Vol. 439, pp.1062-1090, 2013.
[KJJ12] B. Kågström, S. Johansson, and P. Johansson.
StratiGraph Tool: Matrix Stratifications in Control Applications.
In L. Biegler, S. L. Campbell, and V. Mehrmann (Eds.):
Control and Optimization with Differential-Algebraic Constraints,
pp. 79-103, 2012, SIAM Publications. ISBN 978-1-611972-24-5.
Also as Report UMINF 11.12.