A look-ahead Bareiss algorithm for general Toeplit

40RolandW.Freund[40]Zohar,S.(1974):ThesolutionofaToeplitzsetoflinearequations.J.Assoc.Comput.Mach.21,272{276Alook-aheadBareissalgorithmforgeneralToeplitzmatrices39[25]Kailath,T.(1986):AtheoremofI.Schuranditsimpactonmodernsignalprocessing.In:I.Gohberg,ed.,I.SchurMethodsinOperatorTheoryandSignalProcessing.OperatorTheoryAdv.Appl.18,9{30.Birkhauser,Basel[26]Kung,S.-Y.,Hu,Y.H.(1983):AhighlyconcurrentalgorithmandpipelinedarchitectureforsolvingToeplitzsystems.IEEETrans.Acoust.SpeechSignalProcess.ASSP-31,66{76[27]LeRoux,J.,Gueguen,C.(1977):Axedpointcomputationofpartialcorrelationcoecients.IEEETrans.Acoust.SpeechSignalProcess.ASSP-25,257{259[28]Levinson,N.(1946):TheWienerRMS(rootmeansquare)errorcriterioninlterdesignandprediction.J.Math.Phys.25,261{278[29]Morf,M.(1974):Fastalgorithmsformultivariablesystems.Ph.D.Thesis,DepartmentofElectricalEngineering,StanfordUniversity[30]Pal,D.(1990):Fastalgorithmsforstructuredmatriceswitharbitraryrankprole.Ph.D.Thesis,DepartmentofElectricalEngineering,StanfordUniversity[31]Rissanen,J.(1973):AlgorithmsfortriangulardecompositionofblockHankelandToeplitzmatriceswithapplicationtofactoringpositivematrixpolynomials.Math.Comp.27,147{154[32]Schur,I.(1917/18):UberPotenzreihen,dieimInnerndesEinheitskreisesbeschranktsind,PartsIandII.J.ReineAngew.Math.147,205{232,and148,122{145[33]Stoer,J.,Bulirsch,R.(1993):IntroductiontoNumericalAnalysis,SecondEdition.Springer-Verlag,NewYork[34]Sugiyama,Y.(1986):Analgorithmforsolvingdiscrete-timeWiener-HopfequationsbaseduponEuclid’salgorithm.IEEETrans.Inform.TheoryIT-32,394{409[35]Sweet,D.(1993):Theuseofpivotingtoimprovethenumericalperformanceofalgo-rithmsforToeplitzmatrices.SIAMJ.MatrixAnal.Appl.14,468{493[36]Szeg}o,G.(1975):OrthogonalPolynomials,FourthEdition.Amer.Math.Soc.,Provi-dence,R.I.[37]Trench,W.F.(1964):AnalgorithmfortheinversionofniteToeplitzmatrices.J.Soc.Indust.Appl.Math.12,515{522[38]Zarowski,C.J.(1991):SchuralgorithmsforHermitianToeplitz,andHankelmatriceswithsingularleadingprincipalsubmatrices.IEEETrans.SignalProcess.39,2464{2480[39]Zohar,S.(1969):Toeplitzmatrixinversion:thealgorithmofW.F.Trench.J.Assoc.Comput.Mach.16,592{60138RolandW.Freund[12]Durbin,J.(1960):Thettingoftime-seriesmodels.Rev.Inst.Internat.Statist.28,233{243[13]Freund,R.W.(1993):Thelook-aheadLanczosprocessforlargenonsymmetricmatricesandrelatedalgorithms.In:M.S.Moonen,G.H.Golub,andB.L.R.deMoor,eds.,LinearAlgebraforLargeScaleandReal-TimeApplications,pp.137{163.KluwerAcademicPublishers,Dordrecht[14]Freund,R.W.(1993):GeneralizedSzeg}orecurrencesandSchurparametrizationofgen-eralToeplitzmatrices.AT&TNumericalAnalysisManuscript,BellLaboratories,Mur-rayHill,inpreparation[15]Freund,R.W.,Zha,H.(1993):Alook-aheadalgorithmforthesolutionofgeneralHankelsystems.Numer.Math.64,295{321[16]Freund,R.W.,Zha,H.(1993):Formallybiorthogonalpolynomialsandalook-aheadLevinsonalgorithmforgeneralToeplitzsystems.LinearAlgebraAppl.188/189,255{303[17]Gover,M.J.C.,Barnett,S.(1985):InversionofToeplitzmatriceswhicharenotstronglynon-singular.IMAJ.Numer.Anal.5,101{110[18]Gueguen,C.(1981):Linearpredictioninthesingularcaseandthestabilityofeigenmodels.In:Proc.1981IEEEInt.Conf.Acoust.,Speech,SignalProcess.,Atlanta,GA,pp.881{885[19]Gutknecht,M.H.(1993):StablerowrecurrencesforthePadetableandgenericallysuperfastlook-aheadsolversfornon-HermitianToeplitzsystems.LinearAlgebraAppl.188/189,351{421[20]Grenander,U.,Szeg}o,G.(1984):ToeplitzFormsandtheirApplications,SecondEdi-tion.Chelsea,NewYork[21]Heinig,G.,Rost,K.(1984):AlgebraicMethodsforToeplitz-likeMatricesandOpera-tors.Birkhauser,Basel[22]Henkel,W.(1992):AnextendedBerlekamp-MasseyalgorithmfortheinversionofToeplitzmatrices.IEEETrans.Comm.40,1557{1561[23]Ipsen,I.C.F.(1988):Systolicalgorithmsfortheparallelsolutionofdensesymmetricpositive-deniteToeplitzsystems.In:M.Schultz,ed.,NumericalAlgorithmsforModernParallelComputerArchitectures,pp.85{108.Springer-Verlag,NewYork[24]Kac,M.,Murdock,W.L.,Szeg}o,G.(1953):Ontheeigen-valuesofcertainHermitianforms.J.Rat.Mech.Anal.2,767{800Alook-aheadBareissalgorithmforgeneralToeplitzmatrices37AcknowledgmentTheauthorisindebtedtoIlseIpsenforbringingtherecursiveback-substitutionin[10,23]tohisattention.References[1]Ammar,G.S.,Gragg,W.B.(1987):ThegeneralizedSchuralgorithmforthesuperfastsolutionofToeplitzsystems.In:J.Gilewicz,M.Pindor,andW.Siemaszko,eds.,Ra-tionalApproximationanditsApplicationsinMathematicsandPhysics.LectureNotesinMathematics,Vol.1237,pp.315{330.Springer-Verlag,BerlinHeidelbergNewYork[2]Bareiss,E.H.(1969):NumericalsolutionoflinearequationswithToeplitzandvectorToeplitzmatrices.Numer.Math.13,404{424[3]Baxter,G.(1961):Polynomialsdenedbyadierencesystem.J.Math.Anal.Appl.2,223{263[4]Bitmead,R.R.,Anderson,B.D.O.(1980):AsymptoticallyfastsolutionofToeplitzandrelatedsystemsoflinearequations.LinearAlgebraAppl.34,103{116[5]Bojanczyk,A.W.,Brent,R.P.,deHoog,F.R.(1991):OnstabilityofBareissalgorithm.In:F.T.Luk,ed.,AdvancedAlgorithmsandArchitecturesforSignalProcessingII.Proc.SPIE,Vol.1566,pp.23{34[6]Brent,R.P.,Luk,F.T.(1983):Asystolicarray