Eugene Wachspress The ADI Model Problem The ADI Model Problem Eugene Wachspress The ADI Model Problem 123 EugeneWachspress EastWindsor,NewJersey USA Additionalmaterialtothisbookcanbedownloadedfromhttp://extras.springer.com ISBN978-1-4614-5121-1 ISBN978-1-4614-5122-8(eBook) DOI10.1007/978-1-4614-5122-8 SpringerNewYorkHeidelbergDordrechtLondon LibraryofCongressControlNumber:2013933240 ©SpringerScience+BusinessMediaNewYork2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) In lovingmemoryof mywifeof53 years Natalie Preface Thisworkisanupdatededitionofmyself-publishedmonographonTheADIModel Problem [Wachspress, 1995]. Minor typographic corrections have been made in Chaps.1–4. A few innovations have been added such as non-iterative alignment ofcomplexspectrainSect.4.6.In1995thetheorywaspleasingbutapplicationwas limited. With regardto discretized elliptic equations,the restriction to rectangular gridsforwhichreasonableseparableapproximationscouldbegeneratedwaspartic- ularlylimiting.LyapunovandSylvestermatrixequationsopenednewapplications. Although the commutationproperty was no longer a problem there were limiting factorsheretoo.Accurateestimatesforcrucialeigenvalueswererequiredinorder to find effective iteration parameters. This led to a study described in Sect.3.8 in Chap.3ofsimilarityreductiontobandedupperHessenbergformwhichendedwith “Intime,anefficientandrobustschemewillemergeforapplicationtotheLyapunov problem.”SuchaschemeispresentedinChap.5ofthisedition.Crucialeigenvalues includethosewithsmallrealpart,thosewhichsubtendlargeanglesattheoriginand thatoflargestmagnitude.Whenthereducedmatrixisexpressedinsparseformthe MATLABprogramEIGSprovidespreciselythetoolneededforthisdetermination. This left only the limiting fact that ADI, although competitive with methods like Bartels–Stewart [Bartels, 1972], did not offer enough advantage to supplant standard methods. Lack of familiarity of practitioners with the new theory was also detrimental. The saving innovation was that of Penzl [Penzl, 1999]. He demonstratedthattheADIapproachallowedonetoreducearithmeticsignificantly forproblemswith low-rankright-handsides. Thiswas notpossible with the other schemes. Further analysis by Li and White [Li and White, 2002] reduced the arithmetic even further. Now the ADI approach was worthy of consideration by practitioners. It is my hope that it will become the method of choice not only for low-rankproblemsbutalsoformostLyapunovandSylvesterproblems. My programs are all written for serial computation. The ADI approach par- allelizes readily. I have described in Sect.5.7 a scheme for approximating a full symmetricmatrixbyasumoflow-rankmatrices.Eachofthelow-rankmatricesmay be used as a right-hand side in parallel solution of low-rank Lyapunov equations. I only discuss symmetric right-hand sides in Sect.5.7. Sylvester equations have vii viii Preface nonsymmetricright-handsides.BiorthogonalLanczosschemesextendtononsym- metricmatrices.Lanczosdifficultiesassociatedwithnear-zeroinnerproductsmay bepreemptedinthisapproachbyrestarttofindthenextlow-rankcomponent. In 1995 I was still writing FORTRAN programs. I now work exclusively with MATLAB.Chapter6nowincludesMATLABimplementationoftheorydescribed in Chaps.1–5. These programs have treated successfully all my test problems. Theorywas supportedin thatwhencrucial eigenvalueswere computedaccurately theobservederrorreductionagreedwithprediction. This work describes my effort over the past 50 odd years related to theory and application of the ADI iterative method. Although ADI methods enjoyed widespreaduse initially,modelproblemconditionswere notpresentandlittle use was made of the theory related to elliptic functions.The more recentrelevanceto LyapunovandSylvesterequationsstimulatedthefirstsignificantapplication.Iam hopeful that this will lead to further analysis and that other areas of application willbeuncovered.ThatthesimplystatedminimaxproblemdefinedinEqs.8–10in Chap.1couldleadtothetheoryexposedinthisworkhasneverceasedtoamazeme. EastWindsor,NJ EugeneWachspress Contents 1 ThePeaceman–RachfordModelProblem................................. 1 1.1 Introduction............................................................ 1 1.2 ThePeaceman–RachfordMinimaxProblem......................... 3 1.3 EarlyParameterSelection............................................. 8 1.4 OptimumParametersWhenJ D2n.................................. 9 1.5 OptimumParametersfromChebyshevAlternance .................. 11 1.6 EvaluatingtheErrorReduction....................................... 16 1.7 ApproximateParameters.............................................. 20 1.7.1 ErrorReduction................................................ 20 1.7.2 IterationParameters........................................... 21 1.8 UseofOtherDataonSpectraandInitialError....................... 22 2 TheTwo-VariableADIProblem............................................ 25 2.1 RectangularSpectra ................................................... 25 2.2 W.B.Jordan’sTransformation ........................................ 26 2.3 TheThree-VariableADIProblem .................................... 31 2.4 AnalysisoftheTwo-VariableMinimaxProblem .................... 33 2.5 GeneralizedADIIteration............................................. 43 3 ModelProblemsandPreconditioning..................................... 47 3.1 Five-PointLaplacians ................................................. 47 3.2 TheNeutronGroup-DiffusionEquation.............................. 49 3.3 Nine-Point(FEM)Equations.......................................... 51 3.4 ADIModel-ProblemLimitations..................................... 54 3.5 Model-ProblemPreconditioners...................................... 55 3.5.1 PreconditionedIteration....................................... 55 3.5.2 Compound Iteration (Quotations from Wachspress1963) ............................................. 56 3.5.3 UpdatedAnalysisofCompoundIteration.................... 57 3.6 InteractionofInnerandOuterIteration .............................. 59 3.7 Cell-CenteredNodes .................................................. 64 3.8 TheLyapunovMatrixEquation....................................... 64 ix