基于浮点运算的复杂度分析

FloatingPointOperationsinMatrix-VectorCalculus(Version1.3)RaphaelHungerTechnicalReport2007TechnischeUniversitätMünchenAssociateInstituteforSignalProcessingUniv.-Prof.Dr.-Ing.WolfgangUtschickHistoryVersion1.00:October2005-InitialversionVersion1.01:2006-RewriteofsesquilinearformwithareducedamountofFLOPs-SeveralTyposfixedconcerningthenumberofFLOPSrequiredfortheCholeskydecompo-sitionVersion1.2:November2006-ConditionsfortheexistenceofthestandardLLHCholeskydecompositionspecified(pos-itivedefiniteness)-OuterproductversionofLLHCholeskydecompositionremoved-FLOPsrequiredinGaxpyversionofLLHCholeskydecompositionupdated-L1DLH1Choleskydecompositionadded-Matrix-matrixproductLCaddedwithLtriangular-Matrix-matrixproductL1CaddedwithLtriangularandL1notknownapriori-InverseL11ofalowertriangularmatrixwithonesonthemaindiagonaladdedVersion1.3:September2007-FirstgloballyaccessibledocumentversionToDo:(unknownwhen)-QR-Decom[e-mail]52.1MatrixProducts....................................52.1.1Scalar-VectorMultiplicationa.......................52.1.2Scalar-MatrixMultiplicationA......................52.1.3InnerProductaHbofTwoVectors......................52.1.4OuterProductacHofTwoVectors......................52.1.5Matrix-VectorProductAb..........................62.1.6Matrix-MatrixProductAC.........................62.1.7MatrixDiagonalMatrixProductAD....................62.1.8Matrix-MatrixProductLD.........................62.1.9Matrix-MatrixProductL1D.........................62.1.10Matrix-MatrixProductLCwithLLowerTriangular............62.1.11GramAHAofA...............................62.1.12SquaredFrobeniusNormkAk2F=tr(AHA)................72.1.13SesquilinearFormcHAb...........................72.1.14HermitianFormaHRa............................72.1.15GramLHLofaLowerTriangularMatrixL.................72.2Decompositions....................................82.2.1CholeskyDecompositionR=LLH(GaxpyVersion)...........82.2.2CholeskyDecompositionR=L1DLH1...................102.3InversesofMatrices..................................112.3.1InverseL1ofaLowerTriangularMatrixL................112.3.2InverseL11ofaLowerTriangularMatrixL1withOnesontheMainDi-agonal.....................................122.3.3InverseR1ofaPositiveDefiniteMatrixR.................132.4SolvingSystemsofEquations............................132.4.1ProductL1CwithL1notknownapriori.................133.Overview14Appendix15Bibliography1631.IntroductionForthedesignofefficientundlow-complexityalgorithmsinmanysignal-processingtasks,ade-tailedanalysisoftherequirednumberoffloating-pointoperations(FLOPs)isofteninevitable.Mostfrequently,matrixoperationsareinvolved,suchasmatrix-matrixproductsandinversesofmatrices.StructureslikeHermitenessortriangularityforexamplecanbeexploitedtoreducethenumberofneededFLOPsandwillbediscussedhere.Inthistechnicalreport,wederiveexpressionsforthenumberofmultiplicationsandsummationsthatamajorityofsignalprocessingalgorithmsinmobilecommunicationsbringwiththem.Acknowledgments:TheauthorwouldliketothankDipl.-Ing.DavidA.SchmidtandDipl.-Ing.GuidoDietlforthefruitfuldiscussionsonthistopic.42.FlopCountingInthischapter,weofferexpressionsforthenumberofcomplexmultiplicationsandsummationsrequiredforseveralmatrix-vectoroperations.Afloating-pointoperation(FLOP)isassumedtobeeitheracomplexmultiplicationoracomplexsummationhere,despitethefactthatacomplexmul-tiplicationrequires4realmultiplicationsand2realsummationswhereasacomplexsummationsconstistsofonly2realsummations,makingamultiplicationmoreexpensivethanasummation.However,wecounteachoperationasoneFLOP.Throughoutthisreport,weassume2Ctobeascalar,thevectorsa2CN,b2CN,andc2CMtohavedimensionN,N,andM,respectively.ThematricesA2CMN,B2CNN,andC2CNLareassumedtohavenospecialstructure,whereasR=RH2CNNisHermitianandD=diagfd`gN`=12CNNisdiagonal.LisalowertriangularNNmatrix,endenotestheunitvectorwitha1inthen-throwandzeroselsewhere.Itsdimensionalityischosensuchthattherespectivematrix-vectorproductexists.Finally,[A]a;bdenotestheelementinthea-throwandb-thcolumnofA,[A]a:b;c:dselectsthesubmatrixofAconsistingofrowsatobandcolumnsctod.0abistheabzeromatrix.Transposition,Hermitiantransposition,conjugate,andreal-partoperatoraredenotedby(
)T,(
)H,(
),andf
g,respectively,andrequirenoFLOP.2.1MatrixProductsFrequentlyarisingmatrixproductsandtheamountofFLOPsrequiredfortheircomputationwillbediscussedinthissection.2.1.1Scalar-VectorMultiplicationaAsimplemultiplicationaofavectorawithascalarrequiresNmultiplicationsandnosum-mation.2.1.2Scalar-MatrixMultiplicationAExtendingtheresultfromSubsection2.1.1toascalarmatrixmultiplicationArequiresNMmultiplicationsandagainnosummation.2.1.3InnerProductaHbofTwoVectorsAninnerproductaHbrequiresNmultiplicationsandN1summations,i.e.,2N1FLOPs.2.1.4OuterProductacHofTwoVectorsAnouterproductacHrequiresNMmultiplicationsandnosummation.562.FlopCounting2.1.5Matrix-VectorProductAbComputingAbcorrespondstoapplyingtheinnerproductruleaHibfromSubsecti