Forskningsprojekt StratiGraph och MCS Toolbox
StratiGraph är ett Java-baserat verktyg för att beräkna och visa stratifiering (stängningshierarki) av banor eller buntar av kanoniska strukturer. Matrix Canonical Structure (MCS) Toolbox är en Matlab-verktygslåda för att beräkna och representera kanonisk strukturinformation.
SSF, VR, eSSENCE och UMIT (EU Structural Fund Objective 2) har finansierat projektet under alla år. Senaste åren VR och eSSENCE.
Alan Edelman (MIT, Massachusetts) och Paul Van Dooren (UCL, Belgium)
Bestämningen av den kanoniska formen (Jordan, Kronecker, etc.) för en matris eller matrispenna är ett felaktigt problem i närvaro av avrundningsfel när matrisen eller matrispenna har flera defekta eller nedsättande egenvärden. Därför finns det modern numerisk programvara baserad på trappalgoritmer, till exempel GUPTRI, som reglerar dessa problem genom att låta en tolerans för rangbeslut hitta sin struktur.
De algoritmer som används är emellertid kända för att ibland misslyckas och därmed av misstag producera fel men närliggande strukturer. Fel tycks inträffa när matrisen eller matrispenna är nära ett mångfald av intressanta strukturer med högre kodimension.
Alan Edelman, Erik Elmroth och Bo Kågström har föreslagit att utnyttja den matematiska kunskapen om skiktning av föremålen eller buntarna i de kanoniska strukturerna för att förbättra trappalgoritmen. Denna skiktning visar i själva verket vilka strukturer som finns i närheten av andra strukturer (i bemärkelsen att vara i stängningen) i matrisens utrymme. Stratifieringen kan beskrivas som en ansluten graf, som växer exponentiellt med ökande matrisdimension.
StratiGraph är ett Java-baserat mjukvaruverktyg som bestämmer och visualiserar stängning av hirarkiska grafer som är associerade med omlopps- och buntstratifieringar.
Nuvarande version av StratiGraph stöder skiktning av:
• matriser under likhet,
• matrispennor G-sH under strikt ekvivalens,
• styrbarhetspar (A, B) under återkopplingsekvivalens,
• observerbarhetspar (A, C) under injektionsekvivalens,
• icke-singulariserade generaliserade tillstånds-rymdsystem under feedback-injektionsekvivalens, och
• linjärisering av (fullständiga normala) matrispolynom.
Matrix Canonical Structure (MCS) Toolbox för Matlab ger ett ramverk med datatypsobjekt för att representera kanoniska strukturer och beräkningsfunktioner relaterade till kanoniska former. Tillsammans med ett plug-in till StratiGraph är det möjligt att importera och exportera kanoniska strukturer mellan StratiGraph och Matlab.
Nuvarande version av MCS Toolbox stöder kanoniska strukturer av:
• matriser (under likhet, kongruens och *kongruens),
• matrispennor (under strikt ekvivalens och symmetriska och skev-symmetriska pennor under kongruens),
• matrix polynomials,
• systempennor (under feedback-injektionsekvivalens)
MCS -verktygslådan innehåller rutiner för att beräkna den kanoniska strukturinformationen med hjälp av trappalgoritmer. Dessa är baserade på GUPTRI (Generalized UPper TRIangular) algoritm [Demmel & Kågström, 1993] för matrispennor. GUPTRI -formuläret avslöjar den fina kanoniska strukturinformationen för en matrispenna. Till exempel kan vi för en lineariserad modell beräkna dess kanoniska struktur och sedan låta StratiGraph bestämma och visualisera närliggande strukturer i stängningshierarkin.
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.
Book chapter
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.
