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.