ON THE COMPLEXITY OF COMPUTING DETERMINANTS (Exten

ONTHECOMPLEXITYOFCOMPUTINGDETERMINANTS*(Extendedabstract)ERICHKALTOFEN1andGILLESVILLARD21DepartmentofMathematics,NorthCarolinaStateUniversityRaleigh,[e-mail],EcoleNormaleSuperieureLyon46,Alleed'Italie,69364LyonCedex07,[e-mail],~gvillard1IntroductionThecomputationofthedeterminantofannnmatrixAofnumbersorpoly-nomialsisachallengeforbothnumericalandsymbolicmethods.Numericalmethods,suchasClarkson'salgorithm[10,7]forthesignofthedeterminantmustdealwithconditionednessthatdeterminesthenumberofmantissabitsnecessaryforobtainingacorrectsign.SymbolicalgorithmsthatarebasedonChineseremaindering[6,17,Chapter5.5]mustdealwiththefactthatthelengthofthedeterminantintheworstcasegrowslinearlyinthedimensionofthematrix.Hencethenumberofmodularoperationsisntimesthenumberofarithmeticoperationsinagivenalgorithm.Henselliftingcombinedwithra-tionalnumberrecovery[14,1]hascubicbitcomplexityinn,butthealgorithmcanonlydetermineafactorofthedeterminant,namelythelargestinvariantfactor.Ifthematrixissimilartoamultipleoftheidentitymatrix,therunningtimeisagainthatofChineseremaindering.Thetechniquesdevelopedin[32]forcomputingthecharacteristicpoly-nomialofasparsematrixleadtoaspeedupforthegeneral,densedetermi-nantproblem.Forintegermatrices,thebitcomplexitywasshown[16]toben3:5+o(1)(logkAk)2:5+o(1),wherelogkAkmeasuresthelengthoftheen-triesinAandtheexponentadjustmentby\+o(1)capturesmissinglogfactors(\soft-O).Thealgorithmsof[32,16]arerandomizedoftheMonteCarlokind|alwaysfast,probablycorrect|andcanbefurtherspeededbyaThismaterialisbasedonworksupportedinpartbytheNationalScienceFoundationunderGrantsNos.CCR-9988177,DMS-9977392andINT-9726763(Kaltofen).AppearsintheComputerMathematicsProc.FifthAsianSymposium(ASCM2001)editedbyKiyoshiShirayanagiandKazuhiroYokoyama,LectureNotesSeriesonComputing,vol.9,WorldScientic,Singapore,pages13{27.13Strassen/Coppersmith-Winogradsub-cubictimematrixmultiplicationalgo-rithm.NotethatClarkson'salgorithmanditsnewvariantsareintheworstcasequarticinn.Anentirelydierentmethod,basedonanalgorithmin[33],wasrstde-scribedfordensematriceswithpolynomialentries[22].ForintegermatricestheresultingrandomizedalgorithmisoftheLasVegaskind|alwayscorrect,probablyfast|andhasworstcasebitcomplexity(n3:5logkAk)1+o(1)andagaincanbespeededwithsub-cubictimematrixmultiplication.Wegiveadescrip-tionofthisalgorithminSection2below.Thatalgorithmwasoriginallyputtoadierentuse,namelythatofcomputingthecharacteristicpolynomialandadjointofamatrixwithoutdivisions,countingadditions,subtractions,andmultiplicationsinthecommutativeringofentries.Byconsideringabilinearmapwithtwoblocksofvectorsratherthanasinglepairofvectors,Wiedemann'salgorithmcanbeaccelerated[11,23,30,31].Thistechniquecanbeappliedtoourfastdeterminantalgorithm,andresultsinaworstcasebitcomplexityof(n3+1=3logkAk)1+o(1),againbasedonstandardcubictimematrixmultiplication.WediscussthismodicationanditsmathematicaljusticationinSection3.Serendipitously,blockingcanbeappliedtoouroriginal1992division-freealgorithm,andasimilarimprovementofthedivision-freecomplexityofthedeterminantisobtained(seeSection4),thuschangingthestatusofaproblemthathasnowbeenopenforover9years.Inthisextendedabstractwedonotconsidertheuseoffastmatrixmul-tiplicationalgorithms.Byusingthealgorithmsin[13,12]thebitcomplexityforthedeterminantofannnmatrixwithintegerentriescanbereducedtoO(n2:698(logkAk)1+o(1)),andthedivision-freecomplexityofthedeterminantandadjointofamatrixoveracommutativeringtoO(n2:698)ringoperations.Theseexponentshavepurelymathematicalinterestandnoimpactforthecom-putationofadeterminantonacomputer.WeshallalsohidetheexponentsofthelognandloglogkAkfactorsinthe\+o(1)oftheexponents.InSection2weshalladdresstheimpactofthosefactorsonthepracticalityofourmeth-ods.Ingeneral,thepreciseexponentsoftheselogarithmsaredependentontheactualcomputationalmodel,suchasmulti-tapeTuringmachine,logarithmicrandomaccessmachine,hierarchicalmemorymachine,etc.2Wiedemann'salgorithmwithbabysteps/giantstepsAlreadyinhisoriginalpaperWiedemannproposesamethodforcomputingthedeterminantofasparsematrix[33].Thealgorithmisbasedonasequenceofbilinearprojectionsofthepowersoftheinputmatrix.Forvectorsu;v2Kn,whereKisanarbitraryeld,andtheinputmatrixA2Knnconsiderthe14sequenceofeldelementsa0=uTrv;a1=uTrAv;a2=uTrA2v;a3=uTrA3v;:::(1)TheminimalpolynomialofA,denotebyfA,linearlygeneratesfaigi=0;1;:::.BytheBerlekamp/Masseyalgorithmwecancomputeinn1+o(1)arithmeticoperationsaminimallineargeneratorforthesequencefaigi=0;1;:::[5],whichmustbeafactoroffA.HencetheBerlekamp/Masseyalgorithmrequiresatmost2nelementsofthesequence(1).Wiedemannnowrandomlyperturbs(\preconditions)Aandchoosesrandomuandv.Thenwithhighprobabil-itythecharacteristicpolynomialofA,det(IA),isequaltotheminimalrecurrencepolynomialoffaigi=0;1;:::.Theaboveapproachisoriginallyintendedforsparsematrices,wheretheKrylovsequenceAv,A2v;:::canbecomputedeciently.In[22]thefollowingbabysteps/giantstepsapproachisintroducedforcompu