Peter Benner Matthias Bollhöfer Daniel Kressner Christian Mehl Tatjana Stykel Editors Numerical Algebra, Matrix Theory, Diff erential-Algebraic Equations and Control Theory Festschrift in Honor of Volker Mehrmann Numerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory Peter Benner • Matthias BollhoRfer (cid:129) Daniel Kressner (cid:129) Christian Mehl (cid:129) Tatjana Stykel Editors Numerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory Festschrift in Honor of Volker Mehrmann 123 Editors PeterBenner MatthiasBollhoRfer MaxPlanckInstituteforDynamics TUBraunschweig ofComplexTechnicalSystems Carl-Friedrich-Gauß-Fakultät Magdeburg,Germany InstituteComputationalMathematics Braunschweig,Germany DanielKressner ChristianMehl ÉcolePolytechniqueFédéraledeLausanne TUBerlin (EPFL) InstituteofMathematics MATHICSE Berlin,Germany Lausanne,Switzerland TatjanaStykel UniversityofAugsburg InstituteofMathematics Augsburg,Germany ISBN978-3-319-15259-2 ISBN978-3-319-15260-8 (eBook) DOI10.1007/978-3-319-15260-8 LibraryofCongressControlNumber:2015938103 Mathematics Subject Classification (2010): 15A18, 15A21, 15B48, 49M05, 65F08, 65F15, 65H10, 65L80,93B36,93B40,93D09,93D15 SpringerChamHeidelbergNewYorkDordrechtLondon ©SpringerInternationalPublishingSwitzerland2015 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade. Coverillustration:bycourtesyofTatjanaStykel.HandwrittennotesbyVolkerMehrmann,characterizing hisresearchwork Printedonacid-freepaper Springer International Publishing AG Switzerland is part of Springer Science+Business Media (www.springer.com) Preface ThisbookisdedicatedtoVolkerMehrmann,ourmentor,co-author,colleague,and friend. Each chapter in this book highlights one of the many topics Volker has worked on. Inevitably, there are omissions. In this preface, we therefore make an attemptto notonlyconnectthebookchapterstoVolker’sbibliographybutto also provide additional details on topics that receive less attention in the subsequent chapters. M-Matrices andH-Matrices andTheirFriends A complexor real square matrix A is called a Z-matrix if its off-diagonalentries are nonpositive. Equivalently, A D ˛I (cid:2) B holds for some scalar ˛ 2 R and n a nonnegative matrix B. If, additionally, ˛ is not smaller than (cid:2).B/, the spectral radius of B, then A is called an M-matrix. Arising frequently,for example, from thediscretizationofpartialdifferentialequations,matriceswithsuchstructureshave manydesirablepropertiesthatfacilitate,amongotherthings,thedesignandanalysis ofiterativemethodsforsolvinglinearsystems. OstrowskicoinedthetermM-matrixandproposedthefollowinggeneralization: AmatrixAiscalledanH-matrixifitscomparisonmatrixC (definedviac Dja j ii ii andc D(cid:2)ja jfori D1;:::;n,j 6Di)isanM-matrix.Incompletefactorizations ij ij forsuchH-matricesarethetopicofthefirstscientificpaperbyVolkerMehrmann, a1980publication[A1]jointlywithRichardS.VargaandEdwardB.Saff. Apart from M- and H-matrices, there is a myriad of other matrix classes with similarly desirable properties, but different targets in mind. In his 1982 dissertation [T2] and subsequent publications [A2, A3, A5], Volker contributed to this scene by proposing and analyzing the concepts of R- and V-matrices. One major motivation for these new concepts was to find a unified treatment for M-matricesandHermitianpositivesemidefinitematrices. Let the number l.B/ denote the smallest real eigenvalue of a matrix B, with the convention l.B/ D 1 if B has no real eigenvalue. A matrix A is called an v vi Preface Fig.1 YoungVolkerdoing Math !-matrixifthisnumberisfiniteandsatisfiesamonotonicitypropertyforallprinci- palsubmatricesofA.If,moreover,l.A/(cid:3)0,thenAiscalleda(cid:3)-matrix.Sincetheir introductionbyEngelandSchneider,therehasbeensignificantinterestinstudying !- and (cid:3)-matrices because they represent generalizations of several important matrix classes, such as Hermitian matrices, totally nonnegative matrices, and M-matrices. In [A4], Volker showed for n D 4 that every n (cid:4) n (cid:3)-matrix is stable by establishing an eigenvalue inequality conjectured by Varga. More than adecadelater,in1998,OlgaHoltzdisprovedtheconjecturethatthispropertyholds forgeneralnbyconstructingawholefamilyofunstable(cid:3)-matrices. InsubsequentcollaborationswithDanielHershkowitzandHansSchneideronthe matrixclassesdiscussedabove,Volkerinvestigatedlinearpreserverproblems[A9], eigenvalue interlacing properties [A11], and a generalization of sign symmetric matrices[A12].Jointwork[A23]withLudwigElsnerestablishestheconvergence ofblockiterativemethodsforblockgeneralizationsofZ-matricesandM-matrices thatarisefromthediscretizationoftheEulerequationsinfluidflowcomputations. This1991paperalsoseemstomarkatransitionofVolker’sworkintootherareas. HamiltonianandSymplectic Matrices (cid:2) (cid:3) 0 I LetJ D n .AmatrixH 2 R2n(cid:2)2n iscalledHamiltonianif.JH/T D JH (cid:2)I 0 n and a matrix S 2 R2n(cid:2)2n is called symplectic if STJS D J. Hamiltonian and symplecticmatricesseemtohaveacertainfascinationforVolkerthatissharedby severalof his co-authors.On the one hand, there are importantapplications,most notably in optimal and robust control. On the other hand, there is rich algebraic structure: the set of Hamiltonian matrices forms a Lie algebra, and the set of symplectic matrices forms the corresponding Lie group. Additionally to being Preface vii Fig.2 CoverandtableofcontentsofVolker’sDiplomarbeit(equivalenttoaM.Sc.thesis),written inGermanandpre-TEX symmetricwithrespecttotherealline,thespectraofH andS aresymmetricwith respecttotheimaginaryaxisandtheunitcircle,respectively. The analysis and numerical solution of eigenvalue problems for matrices and matrixpencilswithstructureisamajorthreadinVolkerMehrmann’sbibliography, from the first works, his 1979 “Diplomarbeit” [T1] at Bielefeld (see Fig.2 for acopyofthecoverandtableofcontents),untiltoday.Onemajorchallengeinthis field had beenthe developmentof algorithmsthatwouldcomputethe eigenvalues (and invariant subspaces) of Hamiltonian/symplectic matrices in a numerically stable,efficient,andstructure-preservingmanner.Chapter1byBunse-Gerstnerand FaßbenderaswellasChap.4byBennerexplainthesubstantialcontributionsVolker madeinaddressingthischallengeforsmall-tomedium-sizeddensematrices.There have been numerous extensions of the numerical algorithms resulting from this work, most notably to large-scale eigenvalue problems, see Chap.2 by Watkins, andmatrixpencilswithsimilarstructures,seeChap.4aswellasChap.5byPoloni. Their extension to structured matrix polynomialswill be discussed in more detail below. viii Preface Fig.3 VolkerandAngelika Bunse-GerstnerinSan Franciscoduringwhatseems tobeanenjoyable(ofcourse vegetarian!)dinneratGreens RestaurantintheSan Franciscoharborarea,1990 Thereisafascinating,moretheoreticalsidetothestoryonstructuredeigenvalue problems.Still motivatedby algorithmicdevelopments,the 1991paperwith Greg Ammar [A21] discussed the existence (or rather the lack thereof) of structured Hessenberg forms for Hamiltonian and symplectic matrices. This paper is rather unique in not only thanking Angelika Bunse-Gerstner (see Fig. 3 for a picture of her and Volker around this time) for helpful discussions but also “the German police fora speedingticket duringonediscussion”. As summarizedin Chap.6 by MehlandXu, theworkofVolkerandhisco-authorsthenevolvedtowardsa more general picture of structured canonical forms of structured matrices. Perturbation theoryplays a major role in understandingthe potentialbenefits fromstructure in thepresenceofuncertaintyinthematrixentries,forexample,duetoroundofferror. Ofparticularinterestistheperturbationbehaviorofeigenvaluesthatarecriticalin acertainsense,suchaspurelyimaginaryeigenvaluesofHamiltonianmatrices;see Chap.8byBoraandKarowfora summaryofresultsin thisdirection.Chapter13 byRanandRodmangivesamoregeneralsurveyofthestabilityofmatrixanalysis problemswithrespecttoperturbations. Matrix Equations Continuous-time linear-quadratic optimal control problems give rise to algebraic Riccatiequationsoftheform F CATX CXA(cid:2)XGX D0; (0.1) whereA2Rn(cid:2)n,andF;G 2Rn(cid:2)naresymmetricand,often,positivesemidefinite. Undercertainconditions,solutionsX of(0.1)canbeobtainedfromn-dimensional Preface ix Fig.4 Volker organized numerous workshops: one of the first was the 5-day Short Course on Large Scale Scientific Computing in Bielefeld, 1992, jointly organized with Angelika Bunse- Gerstner.Firstencountersofmanyinthispicture invariantsubspacesofthe2n(cid:4)2nHamiltonianmatrix (cid:2) (cid:3) A G : F (cid:2)AT As explained in Chaps.4 and 5, such quadratic matrix equations and their links to structured matrices/matrix pencils have been a major theme in Volker’s work, ever since his 1986 joint work [A6] with Angelika Bunse-Gerstner and his 1987 habilitation thesis [T3, B1]. Among others, this work has led to robust numerical algorithmsforsolvingoptimalandrobustcontrolproblems. In a collaboration with Mihail M. Konstantinov, Petko H. Petkov, and others, theoretical properties of matrix equations have been investigated, establishing a generalframeworkforderivinglocalandnonlocalperturbationbounds.Thiswork, whichhasalsobeenextendedto theperturbationanalysisofeigenvalueproblems, isdescribedinChap.7. Differential-Algebraic Equations A differential-algebraic equation (DAE) arises when one imposes algebraic con- straints on the states of a physical system that is modelled with differential equations. DAEs in all flavors are probably the most central theme of Volker