MATHEMATICS IN INDUSTRY 13 Editors Hans-Georg Bock Frank de Hoog Avner Friedman Arvind Gupta Helmut Neunzert William R. Pulleyblank Torgeir Rusten Fadil Santosa Anna-Karin Tornberg THE EUROPEAN CONSORTIUM FOR MATHEMATICS IN INDUSTRY SUBSERIES Managing Editor Vincenzo Capasso Editors Luis L. Bonilla RRoobbeerrtt MMaatttthheeiijj HHeellmmuutt NNeeuunnzzeerrtt OOttmmaarr SScchheerrzzeerr Wilhelmus H.A. Schilders Henk A. van der Vorst Joost Rommes Editors Model Order Reduction: Theory, Research Aspects and Applications With 133 Figures , 53 in color and 9 Tables 123 AuthorsandEditors WilhelmusH.A.Schilders JoostRommes NXPSemiconductors NXPSemiconductors CorporateI&T/DTF/Design Methods CorporateI&T/DTF/Design Methods PhysicalDesignMethods−Mathematics PhysicalDesignMothods HighTechCampus37 HighTechCampus37 5656AEEindhoven 5656AEEindhoven TheNetherlands TheNetherlands [email protected] [email protected] HenkA.vanderVorst MathematicalInstitute UtrechtUniversity Budapestlaan 6 3508TAUtrecht^ The Netherlands [email protected] ISBN:978-3-540-78840-9 e-ISBN:978-3-540-78841-6 DOI:10.1007/978-3-540-78841-6 LibraryofCongressControlNumber:2008929907 MathematicsSubjectClassification(2000):65,93 (cid:1)c 2008Springer-VerlagBerlinHeidelberg Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation,broadcasting, reproductiononmicrofilmorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9, 1965,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violations areliabletoprosecutionundertheGermanCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnot imply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotective lawsandregulationsandthereforefreeforgeneraluse. Coverdesign:deblik,Berlin Printedonacid-freepaper 987654321 springer.com Preface The idea for this book originated during the workshop “Model order reduction, coupledproblemsandoptimization”heldattheLorentzCenterinLeidenfromSep- tember 19–23, 2005. During one of the discussion sessions, it became clear that a bookdescribingthestateoftheartinmodelorderreduction,startingfromthevery basicsandcontaininganoverviewofallrelevanttechniques,wouldbeofgreatuse forstudents,youngresearchersstartinginthefield,andexperiencedresearchers.The observationthatmostofthetheoryonmodelorderreductionisscatteredovermany goodpapers,makingitdifficulttofindagoodstartingpoint,wassupportedbymost oftheparticipants.Moreover,mostofthespeakersattheworkshopwerewillingto contributetothebookthatisnowinfrontofyou. Thegoalofthisbook,asdefinedduringthediscussionsessionsattheworkshop, is three-fold: first, it should describe the basics of model order reduction. Second, both general and more specialized model order reduction techniques for linear and nonlinearsystemsshouldbecovered,includingtheuseofseveralrelatednumerical techniques.Third,theuseofmodelorderreductiontechniquesinpracticalapplica- tionsandcurrentresearchaspectsshouldbediscussed. We have organized the book according to these goals. In Part I, the rationale behind model order reduction is explained, and an overview of the most common methods is described. Furthermore, in the second chapter, an introduction is given to background material from numerical linear algebra needed to assess the theory andmethodspresentedlaterinthebook.Thisisveryimportantandusefulinforma- tion,asadvancesinnumericallinearalgebraoftenleadtonewresultsintheareaof modelorderreduction.Thus,thefirsttwochaptersserveasanintroductiontoreaders who are not familiar with the subject. In Part II, model order reduction techniques and related numerical problems are described from different points of view: both frameworksforstructure-preservingtechniquesandmorespecializedtechniquesare presented, while numerical methods for (closely) related problems and approaches fornonlinearsystemsareconsideredaswell.Thispartservesasthetheoreticalback- boneofthebook,containinganoverviewoftechniquesusedandareascovered.In PartIIIthefocusisonresearchaspectsandapplicationsofmodelorderreduction.A varietyofexperimentswithreal-lifeexamplesshowsthatdifferentproblemsrequire VI Preface differenttechniques,whileapplicationofthetechniquesleadstonewresearchtopics thataredescribedaswell. Despitethefactthattheworkshopwasorganizedalreadyin2005,thisbookcon- tainsmanyrecentadvancesinmodelorderreduction.Moreover,itpresentsseveral open problems for which techniques arestillindevelopment, related tobothlinear systems, which become larger and more complex mainly due to industrial require- ments, and nonlinear systems, which demand a completely new theory. The latter illustratesthefinalandmostimportantgoalofthisbook,namelytoserveasasource ofinspirationforitsreaders,whowilldiscoverthatmodelorderreductionisavery excitingandlivelyfield. At this point we would like to thank all authors of the chapters in this book. Withoutthecontributionsoftheseexperts,itwouldnotbepossibletocoverthewide andrapidlydevelopingfieldofmodelorderreductioninonebook. Leiden,Utrecht,Eindhoven WilSchilders September2005–May2008 HenkvanderVorst JoostRommes Contents PartI BasicConcepts IntroductiontoModelOrderReduction WilSchilders ..................................................... 3 LinearSystems,Eigenvalues,andProjection HenkvanderVorst ................................................ 33 PartII Theory Structure-PreservingModelOrderReductionofRCLCircuitEquations RolandW.Freund ................................................. 49 A Unified Krylov Projection Framework for Structure-Preserving ModelReduction ZhaojunBai,Ren-cangLi,andYangfengSu ............................ 75 ModelReductionviaProperOrthogonalDecomposition Rene´ Pinnau ..................................................... 95 PMTBR: A Family of Approximate Principal-components-like ReductionAlgorithms JoelR.Phillips,ZhenhaiZhu,andL.MiguelSilveira .....................111 ASurveyonModelReductionofCoupledSystems TimoReisandTatjanaStykel ........................................133 SpaceMappingandDefectCorrection DavidEcheverr´ıa,DomenicoLahaye,andPietW.Hemker.................157 ModalApproximationandComputationofDominantPoles JoostRommes ....................................................177 VIII Contents SomePreconditioningTechniquesforSaddlePointProblems MicheleBenziandAndrewJ.Wathen..................................195 TimeVariantBalancingandNonlinearBalancedRealizations E.I.Verriest ......................................................213 Singular Value Analysis and Balanced Realizations for Nonlinear Systems KenjiFujimotoandJacquelienM.A.Scherpen...........................251 PartIII ResearchAspectsandApplications MatrixFunctions AndreasFrommerandValeriaSimoncini...............................275 ModelReductionofInterconnectedSystems AntoineVandendorpeandPaulVanDooren.............................305 QuadraticInverseEigenvalueProblemandItsApplications toModelUpdating—AnOverview MoodyT.Chu∗∗ ..................................................323 Data-DrivenModelOrderReductionUsingOrthonormalVectorFitting DirkDeschrijverandTomDhaene....................................341 Model-OrderReductionofHigh-SpeedInterconnectsUsingIntegrated CongruenceTransform EmadGad,MichelNakhla,andRamAchar.............................361 ModelOrderReductionforMEMS:MethodologyandComputational EnvironmentforElectro-ThermalModels TamaraBechtold,EvgeniiB.Rudnyi,andJanG.Korvink..................403 ModelOrderReductionofLargeRCCircuits NickP.vanderMeijs ..............................................421 Reduced Order Models of On-Chip Passive Components andInterconnects,WorkbenchandTestStructures DanielIoanandGabrielaCiuprina ...................................447 Index ............................................................. 469 List of Contributors RamAchar GabrielaCiuprina DeptartmentofElectronics PolitehnicaUniversityofBucharest CarletonUniversity Romania Ottawa,ON,Canada,K1S5B6 [email protected] [email protected] DirkDeschrijver ZhaojunBai GhentUniversity DepartmentofComputerScience SintPietersnieuwstraat41 UniversityofCalifornia 9000Gent,Belgium OneShieldsAvenue dirk.deschrijver@intec. Davis,CA95616 ugent.be [email protected] TomDhaene TamaraBechtold GhentUniversity NXPSemiconductors SintPietersnieuwstraat41 HighTechCampus37,WY4.042 9000Gent,Belgium 5656AEEindhoven,TheNetherlands [email protected] [email protected] David Echeverr´ıa MicheleBenzi CWI DepartmentofMathematics Kruislaan413 andComputerScience 1054ALAmsterdam,TheNetherlands EmoryUniversity [email protected] Atlanta,Georgia30322,USA [email protected] RolandW.Freund MoodyT.Chu DepartmentofMathematics DepartmentofMathematics UniversityofCaliforniaatDavis NorthCarolinaStateUniversity OneShieldsAvenue Raleigh,NC27695-8205,USA Davis,CA95616,U.S.A [email protected] [email protected] X ListofContributors AndreasFrommer NickP.vanderMeijs Department of Mathematics and FacultyofEEMCS Science DelftUniversityofTechnology UniversityofWuppertal Delft,TheNetherlands D-42097Wuppertal,Germany [email protected] [email protected] KenjiFujimoto MichelNakhla DepartmentofMechanicalScienceand DeptartmentofElectronics, Engineering CarletonUniversity NagoyaUniversity Ottawa,ON,Canada,K1S5B6 [email protected] [email protected] EmadGad SchoolofInformationTechnologyand JoelR.Phillips Engineering(SITE) CadenceBerkeleyLaboratories UniversityofOttawa Berkeley,CA94704,U.S.A Ottawa,ON,Canada,K1N6N5 [email protected] [email protected] PietW.Hemker Rene´ Pinnau CWI FachbereichMathematik Kruislaan413 TechnischeUniversita¨tKaiserslautern 1054ALAmsterdam,TheNetherlands D-67663Kaiserslautern,Germany [email protected] [email protected] DanielIoan PolitehnicaUniversityofBucharest TimoReis Romania Institutfu¨rMathematik,MA4-5 [email protected] TechnischeUniversita¨tBerlin JanG.Korvink Straßedes17.Juni136 IMTEK,UniversityofFreiburg 10623BerlinGermany Georges-Koehler-Allee102 [email protected] D-79110,Germany [email protected] JoostRommes DomenicoLahaye NXPSemiconductors CWI HighTechCampus37,WY4.042 Kruislaan413 5656AEEindhoven,TheNetherlands 1054ALAmsterdam,TheNetherlands [email protected] [email protected] Ren-cangLi EvgeniiB.Rudnyi DepartmentofMathematics CAD-FEMGmbH UniversityofTexas Marktplatz2 Arlington,TX76019 85567Grafing,Germany [email protected] [email protected]