rkwww

SIAMJ.
APPL.
ALGEBRAGEOMETRYc2017SocietyforIndustrialandAppliedMathematicsVol.
1,pp.
73–110ChordalNetworksofPolynomialIdealsDiegoCifuentesandPabloA.
ParriloAbstract.
Weintroduceanovelrepresentationofstructuredpolynomialideals,whichwerefertoaschordalnetworks.
Thesparsitystructureofapolynomialsystemisoftendescribedbyagraphthatcap-turestheinteractionsamongthevariables.
Chordalnetworksprovideacomputationallyconvenientdecompositionintosimpler(triangular)polynomialsets,whilepreservingtheunderlyinggraphicalstructure.
Weshowthatmanyinterestingfamiliesofpolynomialidealsadmitcompactchordalnetworkrepresentations(ofsizelinearinthenumberofvariables),eventhoughthenumberofcom-ponentsisexponentiallylarge.
Chordalnetworkscanbecomputedforarbitrarypolynomialsystemsusingarenementofthechordaleliminationalgorithmfrom[D.
CifuentesandP.
A.
Parrilo,SIAMJ.
DiscreteMath.
,30(2016),pp.
1534–1570].
Furthermore,theycanbeeectivelyusedtoobtainseveralpropertiesofthevariety,suchasitsdimension,cardinality,andequidimensionalcomponents,aswellasanecientprobabilistictestforradicalidealmembership.
Weapplyourmethodstoex-amplesfromalgebraicstatisticsandvectoradditionsystems;fortheseinstances,algorithmsbasedonchordalnetworksoutperformexistingtechniquesbyordersofmagnitude.
Keywords.
chordalgraphs,structuredpolynomials,chordalnetworks,triangularsetsAMSsubjectclassications.
13P15,14Q99,68W30DOI.
10.
1137/16M106995X1.
Introduction.
Systemsofpolynomialequationscanbeusedtomodelalargevarietyofapplications,andinmostcasestheresultingsystemshaveaparticularsparsitystructure.
Wedescribethissparsitystructureusingagraph.
Anaturalquestionthatarisesiswhetherthisgraphicalstructurecanbeeectivelyusedtosolvethesystem.
In[9]weintroducedthechordaleliminationalgorithm,aneliminationmethodthatalwayspreservesthegraphicalstructureofthesystem.
Inthispaperwerenethisalgorithmtocomputeanewrepresentationofthepolynomialsystemthatwecallachordalnetwork.
ChordalnetworksattempttoxanintrinsicissueofGr¨obnerbases:theydestroythegraphicalstructureofthesystem[9,Ex.
1.
2].
Asaconsequence,polynomialsystemswithsimplestructuremayhaveoverlycomplicatedGr¨obnerbases(seeExample1.
1).
Incon-trast,chordalnetworkswillalwayspreservetheunderlyingchordalgraph.
Weremarkthatchordalgraphshavebeensuccessfullyusedinseveralotherareas,suchasnumericallinearal-gebra[28],discreteandcontinuousoptimization[5,32],graphicalmodels[23],andconstraintsatisfaction[11].
Chordalnetworksdescribeadecompositionofthepolynomialidealintosimpler(trian-gular)polynomialsets.
ThisdecompositiongivesquitearichdescriptionoftheunderlyingReceivedbytheeditorsApril11,2016;acceptedforpublication(inrevisedform)November2,2016;publishedelectronicallyFebruary1,2017.
http://www.
siam.
org/journals/siaga/1/M106995.
htmlFunding:ThisresearchwassupportedbyAFOSRundergrantFA9550-11-1-0305.
LaboratoryforInformationandDecisionSystems(LIDS),MassachusettsInstituteofTechnology,Cambridge,MA02139(diegcif@mit.
edu,parrilo@mit.
edu).
7374DIEGOCIFUENTESANDPABLOA.
PARRILOvariety.
Inparticular,chordalnetworkscanbeecientlyusedtocomputedimension,cardinal-ity,andequidimensionalcomponentsandalsototestradicalidealmembership.
Remarkably,severalfamiliesofpolynomialideals(withexponentiallylargeGr¨obnerbases)admitacom-pactchordalnetworkrepresentationofsizeproportionaltothenumberofvariables.
Wewillshortlypresentsomemotivationalexamplesaftersettingupthemainterminology.
ThroughoutthisdocumentweworkinthepolynomialringK[X]=K[x0,x1,xn1]oversomeeldK.
Wexonceandforalltheorderingofthevariablesx0>x1xn1.
1WeconsiderasystemofpolynomialsF={f1,f2,fm}.
ThereisanaturalgraphG(F),withvertexsetX={x0,xn1},thatabstractsthesparsitystructureofF.
Thegraphisgivenbycliques:foreachfiweaddacliqueinallitsvariables.
Equivalently,thereisanedgebetweenxiandxjifandonlyifthereissomepolynomialinFthatcontainsbothvariables.
WewillconsiderthroughoutthepaperachordalcompletionGofthegraphG(F),andwewillassumethatx0xn1isaperfecteliminationorderingofG(seeDenition2.
1).
Somemotivatingexamples.
Thenotionsofchordalityandtreewidthareubiquitousinappliedmathematicsandcomputerscience.
Inparticular,severalhardcombinatorialprob-lemscanbesolvedecientlyongraphsofsmalltreewidthbyusingsometypeofrecursion(ordynamicprogram)[5].
Wewillseethatthisrecursivenatureisalsopresentinseveralpolynomialsystemsofsmalltreewidth.
Wenowillustratethiswiththreesimpleexamples.
Example1.
1(coloringacyclegraph).
GraphcoloringisaclassicalNP-completeproblemthatcanbesolvedecientlyongraphsofsmalltreewidth.
WeconsiderthecyclegraphCnwithvertices0,1,n1,whosetreewidthistwo.
ColoringCnisparticularlysimplebyproceedinginarecursivemanner:colorvertexn1arbitrarily,andthensubsequentlycolorvertexi,avoidingthecolorofi+1andpossiblyn1.
Theq-coloringproblemforagraphG=(V,E)canbeencodedinasystemofpolynomialequations(see,e.
g.
,[10]):xqi1=0,i∈V,(1a)xq1i+xq2ixjxixq2j+xq1j=0,ij∈E.
(1b)LetFn,qdenotesuchasystemofpolynomialsforthecyclegraphCn.
Giventhatcoloringthecyclegraphissoeasy,itshouldbepossibletosolvetheseequationseciently.
However,ifwecomputeaGr¨obnerbasis,theresultisnotsosimple.
Inparticular,forthecaseofF9,3oneofthesepolynomialshas81terms(withbothlexandgrevlexorder).
ThisisaconsequenceofthefactthatGr¨obnerbasesdestroythegraphicalstructureoftheequations.
Nonetheless,onemayhopetogiveasimplerepresentationoftheabovepolynomialsthattakesintoaccounttheirrecursivenature.
Indeed,atriangulardecompositionoftheseequa-tionsispresentedinFigure1forthecaseofF9,3,andthepatternisverysimilarforarbitraryvaluesofn,q.
ThedecompositionrepresentedisV(F9,3)=TV(T),1Observethatsmallerindicescorrespondtolargervariables.
CHORDALNETWORKSOFPOLYNOMIALIDEALS75x20+x0x8+x28x0+x1+x8x1x8x21+x1x8+x28x1+x2+x8x22+x2x8+x28x2+x3+x8x2x8x3x8x23+x3x8+x28x3+x4+x8x24+x4x8+x28x4+x5+x8x4x8x5x8x25+x5x8+x28x5+x6+x8x6+x7+x8x6x8x27+x7x8+x28x381012345678Figure1.
Chordalnetworkforthe3-chromaticidealofacycle.
wheretheunionisoverallmaximaldirectedpathsinthediagramofFigure1.
OnepathisT={x0+x1+x8,x21+x1x8+x28,x2x8,x23+x3x8+x28,x4x8,x25+x5x8+x28,x6x8,x27+x7x8+x28,x381}.
Recallthatasetofpolynomialsistriangularifthelargestvariablesofthesepolynomialsarealldistinct,andobservethatallmaximalpathsTaretriangular.
Notethatthetotalnumberoftriangularsetsis21,andingeneralwegetthe(n1)stFibonaccinumber.
Eventhoughthesizeofthetriangulardecompositiongrowsrapidly,itadmitsaverycompactrepresentation(linearinn),andthereasonispreciselytherecursivenatureoftheequations.
Indeed,thediagramofFigure1isconstructedinawayverysimilartohowweconstructcolorings:choosex8arbitrarily;thenforeachxichooseitbasedonthevaluesofxi+1andx8.
Example1.
2(vertexcoversofatree).
Wenowconsidertheproblemofndingminimumvertexcoveringsofagraph.
RecallthatasubsetSofverticesisacoverifanyedgeisincidenttoatleastoneelementinS.
Sincethecomplementofavertexcoverisanindependentset,computingaminimumvertexcoverisNP-complete.
Nevertheless,whenthegraphisatree,theminimalvertexcovershaveaveryspecialstructure.
Indeed,wecanconstructsuchacoverrecursively,startingfromtheroot,asfollows.
Fortherootnode,wecandecidewhethertoincludeitinthecoverornot.
Ifweincludeit,wecandeletetherootandthenrecurseoneachofitschildren.
Otherwise,weneedtoincludeinthecoverallofitschildren,sowecandeletethemall,andthenrecurse.
TheminimalvertexcoversofagraphG=(V,E)areincorrespondencewiththeirreduciblecomponentsofitsedgeidealI(G):=xixj:ij∈E(see,e.
g.
,[33,Prop.
7.
2.
3]).
Therefore,theirreduciblecomponentsoftheedgeidealofatreealwayshaveaverysimplestructure(althoughtheremightbeexponentiallymany).
Forinstance,thediagraminFigure2representsthecomponentsforthecaseofasimple10-vertextree.
Herethecomponentsaregivenbythe76DIEGOCIFUENTESANDPABLOA.
PARRILO0x00x10x20x30x40x50x60x70x80x90123456789Figure2.
Chordalnetworkfortheedgeidealofatree.
possiblechoicesofonenodefromeachofthe(purple)boxessothatthesenodesareconnected(e.
g.
,T={0,0,0,x3,x4,x5,x6,0,x8,0}).
Notethatthereare24+1=17components.
Example1.
3(adjacentminors).
LetXbea2*nmatrixofindeterminates,andconsiderthepolynomialsetFngivenbyitsadjacentminors,i.
e.
,X:=x0x2···x2n2x1x3···x2n1,Fn:={x2ix2i+3x2i+1x2i+2:0≤iingidealhasbeenstudiedin,e.
g.
,[13,16].
Figure3showsthegraphassociatedtothissystem.
WeareinterestedindescribingtheirreduciblecomponentsofV(Fn).
x0x3x1x20x2x5x3x40x2,x3x4x7x5x60x4,x5x6x9x7x80x6,x7x8x11x9x100x8,x9x10x13x11x120x10,x11x12x15x13x14x12,x130012345678910,1112,1314,15Figure3.
Chordalnetworkfortheidealofadjacentminors.
AsinExample1.
1,thereisasimplerecursiveproceduretoproducepointsonV(Fn):wechoosethevaluesofthelastcolumnofthematrixarbitrarily,andthenforcolumniweeitherchooseitarbitrarily,inthecasethatcolumni+1iszero,orscalecolumni+1ifitisnonzero.
Thisprocedureisactuallydescribingtheirreduciblecomponentsofthevariety.
Inthisway,theirreduciblecomponentsadmitacompactdescription,whichisshowninFigure3.
Again,thecomponentsaregivenbythemaximaldirectedpaths(e.
g.
,T={0,x2,x3,0,x6,x7,x8x11x9x10,0,x12,x13,0}),anditscardinalityisthenthFibonaccinumber.
CHORDALNETWORKSOFPOLYNOMIALIDEALS77Contributions.
Theexamplesaboveshowhowcertainpolynomialsystemswithtree-likestructureadmitacompactchordalnetworkrepresentation.
Theaimofthispaperistodevelopageneralframeworktosystematicallyunderstandandcomputechordalnetworks.
Wealsostudyhowtoeectivelyusechordalnetworkstosolvedierentproblemsfromcomputationalalgebraicgeometry.
Amajordicultyisthatexponentiallymanytriangularsetsmayappear(e.
g.
,theFibonaccinumberinExample1.
1).
Thispaperpresentsthefollowingcontributions:Weintroducethenotionofchordalnetworks,anovelrepresentationofpolynomialidealsaimedtowardexploitingstructuredsparsity.
Wedevelopthechordaltriangularizationmethod(Algorithm1)tocomputesuchchordalnetworkrepresentation.
ItscorrectnessisestablishedinTheorems3.
9and6.
10.
Weshowthatseveralfamiliesofpolynomialsystemsadmita"small"chordalnetworkrepresentation,ofsizeO(n).
Thisistrueforcertainzero-dimensionalideals(Re-mark3.
23),allmonomialideals(Theorem5.
3),andcertainbinomial/determinantalideals(section7.
3),althoughingeneralthiscannotbeguaranteed(Remark3.
25).
Weshowhowtoeectivelyusechordalnetworkstocomputeseveralpropertiesoftheunderlyingvariety.
Inparticular,thecardinality(section4.
2),dimension,andtop-dimensionalcomponent(section5.
2)canbecomputedinlineartime.
Insomeinterestingcaseswecanalsodescribetheirreduciblecomponents.
WepresentaMonteCarloalgorithmtotestradicalidealmembership(Algorithm3).
WeshowinTheorem4.
3thatthecomplexityislinearwhenthegivenpolynomialpreservessomeofthegraphicalstructureofthesystem.
WepointoutthatwehaveapreliminaryimplementationofaMacaulay2packagewithallthemethodsfromthispaper,anditisavailableatwww.
mit.
edu/diegcif.
Structureofthepaper.
Theorganizationofthispaperisasfollows.
Insection2wereviewtheconceptofchordalgraphandthenformalizethenotionofchordalnetwork.
Wethenproceedtoexplainourmethods,initiallyonlyforarestrictedclassofzero-dimensionalproblems(section3andsection4),thenforthecaseofmonomialideals(section5),andnallyconsideringthefullygeneralcase(section6).
Weconcludethepaperinsection7withnumericalexamplesofourmethods.
Thereasonforpresentingourresultsinthisstepwisemanneristhatthegeneralcaserequireshighlytechnicalconceptsfromthetheoryoftriangularsets.
Indeed,weencouragethereaderunfamiliarwithtriangularsetstoomitsection6ontherstread.
Ontheotherhand,byrstspecializingourmethodstothezero-dimensionalandmonomialcases,wecanintroducethemallinatransparentmanner.
Importantly,thebasicstructureofthechordaltriangularizationalgorithm,presentedinsection3,remainsthesameforthegeneralcase.
Similarly,ouralgorithmsthatusechordalnetworkstocomputepropertiesofthevariety(e.
g.
,cardinality,dimension)introducedinsection4andsection5alsoextendinanaturalway.
Relatedwork.
Thedevelopmentofchordalnetworkscanbeseenasacontinuationofourearlierwork[9],andwereferthereadertothatpaperforadetailedsurveyoftherelevantliteratureongraphicalstructureincomputationalalgebraicgeometry.
Forthisreason,belowweonlydiscussrelatedworkinthecontextoftriangularsets,andwepointoutthemaindierencesbetweenthispaperand[9].
78DIEGOCIFUENTESANDPABLOA.
PARRILOThispaperimprovesupon[9]intwomainareas.
First,chordalnetworksprovideamuchricherdescriptionofthevarietythantheeliminationidealsobtainedbychordalelimination.
Forinstance,theeliminationidealsoftheequationsfromExample1.
3aretrivial,butitschordalnetworkrepresentationrevealsitsirreduciblecomponents.
Inaddition,neitherthedimension,northecardinality,northeradicalidealmembershipcanbedirectlycomputedfromtheeliminationideals(weneedaGr¨obnerbasis).
Second,weshowhowtocomputechordalnetworkrepresentationsforarbitrarypolynomialsystems(incharacteristiczero).
Incontrast,chordaleliminationonlycomputestheeliminationidealsundercertainassumptions.
Thereisabroadliteraturestudyingtriangulardecompositionsofideals[3,19,24,26,36].
However,pastworkhasnotconsideredthecaseofsparsepolynomialsystems.
Amongthemanyexistingtriangulardecompositionalgorithms,Wang'seliminationmethodsareparticu-larlyrelevanttous[36,37].
AlthoughseeminglyunnoticedbyWang,mostofhisalgorithmspreservethechordalstructureofthesystem.
Asaconsequence,wehaveexperimentallyseenthathismethodsaremoreecientthanthosebasedonregularchains[25,26]fortheexamplesconsideredinthispaper.
Asopposedtopreviouswork,weemphasizechordalnetworksasourcentralobjectofstudy,ratherthantheexplicittriangulardecompositionobtained.
Thisisakeydistinctionsinceforseveralfamiliesofidealsthesizeofthechordalnetworkislineareventhoughthecorrespondingtriangulardecompositionhasexponentialsize(seetheexamplesfromabove).
Inaddition,ourmethodsdeliberatelytreattriangulardecompositionsasablackboxalgorithm,allowingustouseeitherLazard'sLexTriangularalgorithm[24]forthezero-dimensionalcaseorWang'sRegSeralgorithm[35]forthepositive-dimensionalcase.
2.
Chordalnetworks.
2.
1.
Chordalgraphs.
Chordalgraphshavemanyequivalentcharacterizations.
Agoodpresentationisfoundin[4].
Forourpurposes,weusethefollowingdenition.
Denition2.
1.
LetGbeagraphwithverticesx0,xn1.
Anorderingofitsverticesx0>x1xn1isaperfecteliminationorderingifforeachxlthesetXl:={xl}∪{xm:xmisadjacenttoxl,xminationordering.
Remark2.
2.
Observethatlowerindicescorrespondtolargervertices.
Chordalgraphshavemanyinterestingproperties.
Forinstance,theyhaveatmostnmaximalcliques,giventhatanycliqueiscontainedinsomeXl.
Notethattreesarechordalgraphs,sincebysuccessivelypruningaleaffromthetreewegetaperfecteliminationordering.
Wecanalwaysndaperfecteliminationorderingofachordalgraphinlineartime[28].
Denition2.
3.
LetGbeanarbitrarygraph.
WesaythatGisachordalcompletionofGifitischordalandGisasubgraphofG.
ThecliquenumberofG,denotedasκ,isthesizeofitslargestclique.
ThetreewidthofGistheminimumcliquenumberofG(minusone)amongallpossiblechordalcompletions.
CHORDALNETWORKSOFPOLYNOMIALIDEALS79Observethatgivenanyorderingx0xn1oftheverticesofG,thereisanaturalchordalcompletionG;i.
e.
,weaddedgestoGinsuchawaythateachG|Xlisaclique.
Ingeneral,wewanttondachordalcompletionwithasmallcliquenumber.
However,therearen!
possibleorderingsofthevertices,andthusndingthebestchordalcompletionisnotsimple.
Indeed,thisproblemisNP-hard[2],buttherearegoodheuristicsandapproximationalgorithms[5,32].
See[6]foracomparisonofsomeoftheseheuristics.
(a)Chordalcompletion(b)EliminationtreeFigure4.
Left:10-vertexgraph(blue/solid)andachordalcompletion(green/dashed).
Right:Eliminationtreeofthechordalcompletion.
Example2.
4.
LetGbetheblue/solidgraphinFigure4a.
Thisgraphisnotchordal,butifweaddthesixgreen/dashededgesshowninthegure,weobtainachordalcompletionG.
Infact,theorderingx0x9isaperfecteliminationorderingofthechordalcompletion.
ThecliquenumberofGisfour,andthetreewidthofGisthree.
Asmentionedearlier,wewillassumethroughoutthisdocumentthatthepolynomialsys-temFissupportedonagivenchordalgraphG,wherebysupportedwemeanthatGisachordalcompletionofG(F).
Moreover,weassumethattheorderingofthevertices(inheritedfromthepolynomialring)isaperfecteliminationorderingofG.
GivenachordalgraphGwithsomeperfecteliminationordering,thereisanassociatedtreethatwillbeveryhelpfulinourdiscussion.
Denition2.
5.
LetGbeanorderedgraphwithverticesx0xn1.
TheeliminationtreeofGisthefollowingdirectedspanningtree:foreachlthereisanarcfromxltowardthelargestxpthatisadjacenttoxlandxpinationtreeisrootedatxn1.
Figure4bshowsanexampleoftheeliminationtree.
Wenowpresentasimplepropertyoftheeliminationtreeofachordalgraph.
Lemma2.
6.
LetGbeachordalgraph,letxlbesomevertex,andletxpbeitsparentintheeliminationtreeT.
ThenXl\{xl}Xp,whereXiisasin(2).
Proof.
LetY:=Xl\{xl}.
NotethatYisaclique,whoselargestvariableisxp.
SinceXpistheuniquelargestcliquesatisfyingsuchaproperty,wemusthaveYXp.
2.
2.
Chordalnetworks.
Weproceedtoformalizetheconceptofchordalnetworks.
80DIEGOCIFUENTESANDPABLOA.
PARRILODenition2.
7.
LetGbeachordalgraphwithvertexsetX,andletXlbeasin(2).
AG-chordalnetworkisadirectedgraphN,whosenodesarepolynomialsetsinK[X],suchthatthefollowinghold:(Nodessupportedoncliques)EachnodeFlofNisgivenarankl=rk(Fl),with0≤linationtree)If(Fl,Fp)isanarcofN,then(l,p)isanarcoftheeliminationtreeofG,wherel=rk(Fl),p=rk(Fp).
Achordalnetworkistriangularifeachnodeconsistsofasinglepolynomialf,andeitherf=0oritslargestvariableisxrk(f).
Thereisoneparameterofachordalnetworkthatwilldeterminethecomplexityofsomeofourmethods.
Thewidthofachordalnetwork,denotedasW,isthelargestnumberofnodesofanygivenrank.
NotethatthenumberofnodesinthenetworkisatmostnW,andthenumberofarcsisatmost(n1)W2.
Wecanrepresentchordalnetworksusingthediagramswehaveshownthroughoutthepaper.
Sincethestructureofachordalnetworkresemblestheeliminationtree(seconditeminthedenition),weusuallyshowtheeliminationtreetotheleftofthenetwork.
g(a,b,c):=a2+b2+c2+ab+bc+cax30+x20x7+x0x27+x37g(x0,x6,x7)x31+x21x9+x1x29+x39g(x1,x4,x9)x32+x22x5+x2x25+x35g(x2,x3,x5)x3x5g(x3,x7,x8)x3+x5+x7+x8x4x9g(x4,x8,x9)x4+x5+x8+x9g(x5,x8,x9)x5+x7+x8+x9x5x9x5x7x5x9x6x7g(x6,x8,x9)x6+x7+x8+x9x7x9g(x7,x8,x9)x38+x28x9+x8x29+x39x4910123456789Figure5.
G-chordalnetwork,whereGisthechordalgraphfromFigure4a.
TheeliminationtreeofGisshownontheleft.
Example2.
8.
LetGbetheblue/solidgraphfromFigure4a,andletGbethegreen/dashedchordalcompletion.
Figure5showsaG-chordalnetworkofwidth5thatrepresentsthe4-coloringsofgraphG(equation(1)).
TheeliminationtreeofGisshowntotheleftofthediagram.
Notethatthisnetworkistriangular,andthusallitsnodesconsistofasinglepolynomial.
Forinstance,twoofitsnodesaref5=x5+x7+x8+x9andf6=x6x7.
Nodesaregroupedinbluerectangularboxesaccordingtotheirrank.
Inparticular,f5hasrank5andf6rank6,andindeedf5∈K[X5]=K[x5,x7,x8,x9]andf6∈K[X6]=K[x6,x7,x8,x9].
CHORDALNETWORKSOFPOLYNOMIALIDEALS81Example2.
9.
LetGbethe9-cyclewithverticesx0,x8.
LetGbethechordalcomple-tionobtainedbyconnectingvertexx8toalltheothers.
Figure1showsatriangularG-chordalnetwork.
Theeliminationtree,showntotheleftofthenetwork,isthepathx0x8.
Remark2.
10.
Sometimeswecollapsecertainrankstomakethediagramvisuallysimpler.
Inparticular,inFigure3wecollapsetheranks2i,2i+1intoasinglegroup.
Assuggestedbytheexamplesintheintroduction,atriangularchordalnetworkgivesade-compositionofthepolynomialidealintotriangularsets.
Eachsuchtriangularsetcorrespondstoachainofthenetwork,asdenednext.
Denition2.
11.
LetNbeaG-chordalnetwork.
AchainofNisatupleofnodesC=(F0,F1,Fn1)suchthatthefollowinghold:rk(Fl)=lforeachl.
Ifxpistheparentofxl,then(Fl,Fp)isanarcofN.
Example2.
12.
ThechordalnetworkfromFigure5has21chains,oneofwhichisC=(x20+x0x6+x0x7+x26+x6x7+x27,x31+x21x9+x1x29+x39,x32+x22x5+x2x25+x35,x3x5,x4x9,x25+x5x8+x5x9+x28+x8x9+x29,x26+x6x8+x6x9+x28+x8x9+x29,x7x9,x38+x28x9+x8x29+x39,x491).
2.
3.
Binarydecisiondiagrams.
Althoughmotivatedfromadierentperspectiveandwithquitedistinctgoals,throughoutthedevelopmentofthispaperwerealizedtheintriguingsimilaritiesbetweenchordalnetworksandaclassofdatastructuresusedincomputerscienceknownasorderedbinarydecisiondiagrams(OBDDs)[1,7,21,38].
Abinarydecisiondiagram(BDD)isadatastructurethatcanbeusedtorepresentBoolean(binary)functionsintermsofadirectedacyclicgraph.
Theycanbeinterpretedasabinaryanalogueofastraight-lineprogram,wherethenodesareassociatedwithvariablesandtheoutgoingedgesofanodecorrespondtothepossiblevaluesofthatvariable.
AparticularlyimportantsubclassaretheOBDDs,wherethebranchingoccursaccordingtoaspecicxedvariableordering.
Underamildcondition(reducibility)thisrepresentationcanbemadeunique,andthuseveryBooleanfunctionhasacanonicalOBDDrepresentation.
OBDDscanbeeectivelyusedforfurthermanipulation(e.
g.
,decidesatisability,countsatisfyingassignments,computelogicaloperations).
Interestingly,severalimportantfunctionshaveacompactOBDDrepresentation.
Afurthervariation,zero-suppressedBDDs(ZBDDs),canbeusedtoecientlyrepresentsubsetsofthehypercube{0,1}nandtomanipulatethem(e.
g.
,intersections,sampling,linearoptimization).
ChordalnetworkscanbethoughtofasawidegeneralizationofOBDDs/ZBDDstoar-bitraryalgebraicvarietiesovergeneralelds(insteadofnitesetsin(F2)n).
Likechordalnetworks,anOBDDcorrespondstoacertaindirectedgraph,butwherethenodesarevari-ables(x0,x1,insteadofpolynomialsets.
Wewillseeinsection5thatforthespeciccaseofmonomialideals,theassociatedchordalnetworksalsohavethisform.
Sinceoneofourmaingoalsistopreservegraphicalstructureforecientcomputation,inthispaperwedenechordalnetworksonlyforsystemsthatarestructuredaccordingtosomechordalgraph.
Inaddition,forcomputationalpurposeswedonotinsistonuniquenessoftherepresentation(althoughitmightbepossibletomakethemcanonicalafterfurtherprocessing).
82DIEGOCIFUENTESANDPABLOA.
PARRILOThepracticalimpactofdatastructureslikeBDDsandOBDDsoverthepastthreedecadeshasbeenverysignicant,astheyhaveenabledbreakthroughresultsinmanyareasofcomputerscience,includingmodelchecking,formalverication,andlogicsynthesis.
Wehopethatchordalnetworkswillmakepossiblesimilaradvancesincomputationalalgebraicgeometry.
TheconnectionsbetweenBDDsandchordalnetworksrunmuchdeeper,andweplantofurtherexploretheminthefuture.
3.
Thechordallyzero-dimensionalcase.
Inthissectionwepresentourmainmeth-odstocomputetriangularchordalnetworks,althoughfocusedonarestrictedtypeofzero-dimensionalproblems.
Thisrestrictionisforsimplicityonly;wewillseethatourmethodsnaturallyextendtoarbitraryideals.
Concretely,weconsiderthefollowingfamilyofpolyno-mialsets.
Denition3.
1(chordallyzero-dimensional).
LetFK[X]besupportedonachordalgraphG.
WesaythatFischordallyzero-dimensionalifforeachmaximalcliqueXlofgraphGtheidealF∩K[Xl]iszero-dimensional.
Notethattheq-coloringequationsin(1)arechordallyzero-dimensional.
AsinExam-ple1.
1,chordallyzero-dimensionalproblemsalwayshavesimplechordalnetworkrepresenta-tions.
Remark3.
2(thegeometricpicture).
Thereisanicegeometricinterpretationbehindthechordallyzero-dimensionalcondition.
DenotingVlthevarietyofF∩K[Xl],theconditionisthateachVlisnite.
NotenowthatπXl(V(F))Vl,whereπXldenotestheprojectionontothecoordinatesofXl.
Thus,independentofthesizeofV(F),thechordallyzero-dimensionalconditionallowsustoboundthesizeofitsprojectionsontoeachXl.
Moregenerally,althoughnotelaboratedinthispaper,ourmethodsareexpectedtoperformwellonanyF(possiblypositive-dimensional)forwhichtheprojectionsπXl(V(F))arewellbehaved.
3.
1.
Triangularsets.
Wenowrecallthebasicconceptsoftriangularsetsforthecaseofzero-dimensionalideals,following[24].
Wedelaytheexpositionofthepositive-dimensionalcasetosection6.
Denition3.
3.
Letf∈K[X]\Kbeanonconstantpolynomial.
Themainvariableoff,denotedmvar(f),isthegreatestvariableappearinginf.
Theinitialoff,denotedinit(f),istheleadingcoecientoffwhenviewedasaunivariatepolynomialinmvar(f).
Azero-dimensionaltriangularsetisacollectionofnonconstantpolynomialsT={t0,tn1}suchthatmvar(ti)=xiandinit(ti)=1foreachi.
MostoftheanalysisdoneinthispaperwillworkoveranarbitraryeldK.
Forsomeresultswerequiretheeldtocontainsucientlymanyelements,sowemightneedtoconsideraeldextension.
WedenotebyKthealgebraicclosureofK.
ForapolynomialsetF,weletV(F)Knbeitsvariety.
Notethatforazero-dimensionaltriangularsetT,wealwayshave|V(T)|≤deg(T):=t∈Tmdeg(t),(3)wheremdeg(t):=deg(t,mvar(t))denotesthedegreeonthemainvariable.
Furthermore,theaboveisanequalityifwecountmultiplicities.
CHORDALNETWORKSOFPOLYNOMIALIDEALS83ForatriangularsetT,letTdenotethegeneratedideal.
Itiseasytoseethatazero-dimensionaltriangularsetisalexicographicGr¨obnerbasisofT.
Inparticular,wecantestidealmembershipbytakingnormalform.
Wealsodenoteaselimp(T):=T∩K[xp,xp+1,.
.
.
]thesubsetofTrestrictedtovariableslessthanorequaltoxp.
Notethatelimp(T)generatestheeliminationidealofTbecauseoftheeliminationpropertyoflexicographicGr¨obnerbases.
Notation.
WeletS=S1S2denoteadisjointunion,i.
e.
,S=S1∪S2andS1∩S2=.
Denition3.
4.
LetIK[X]beazero-dimensionalideal.
AtriangulardecompositionofIisacollectionToftriangularsets,suchthatV(I)=T∈TV(T).
WesaythatTissquare-freeifeachT∈Tgeneratesaradicalideal.
WesaythatTisirreducibleifeachT∈Tgeneratesaprimeideal(or,equivalently,amaximalideal).
LazardproposedalgorithmstocomputeatriangulardecompositionfromaGr¨obnerba-sis[24].
Healsoshowedhowtopostprocessittomakeitsquare-free/irreducible.
Remark3.
5.
Asexplainedin[24],theremightbeseveraldistincttriangulardecomposi-tionsofanideal,buttherearesimplewaystopassfromonedescriptiontoanother.
3.
2.
Chordaltriangularization.
WeproceedtoexplainhowtocomputeatriangularchordalnetworkrepresentationofapolynomialsetF.
Wewillstartwithaparticular(in-duced)chordalnetworkthatismodiedstepaftersteptomakeittriangular.
Denition3.
6.
LetFK[X]besupportedonachordalgraphG.
TheinducedG-chordalnetworkhasauniquenodeofrankk,namelyFk:=F∩K[Xk],anditsarcsarethesameasintheeliminationtree;i.
e.
,(Fl,Fp)isanarcifxpistheparentofxl.
Wewillsequentiallyperformtwotypesofoperationstotheinducedchordalnetwork.
Triangulate(Fl).
LetTbeatriangulardecompositionofanodeFlofthenetwork.
ReplacenodeFlwithonenodeforeachtriangularsetinT.
AnynodewhichwaspreviouslyconnectedtoFlisthenconnectedtoeachofthenewnodes.
Eliminate(T).
LetTbearanklnode,andletxpbetheparentofxl.
LetTp:=elimp(T)andTl:=T\Tp.
Foreacharc(T,Fp)wecreateanewrankpnodeFp:=Fp∪Tp,andwesubstitutearc(T,Fp)with(T,Fp).
Then,wecopyallarcscomingoutofFptoFp(whilekeepingtheoldarcs).
Next,wereplacethecontentofnodeTwiththepolynomialsetTl.
Theoperationsareperformedinrounds:inthelthroundwetriangulate/eliminateallranklnodes.
Aftereachround,wemayreducethenetworkwiththefollowingadditionaloperations.
MergeIn(l).
MergeanytworanklnodesFl,Fliftheydenethesameideal,andtheyhavethesamesetsofincomingarcs.
MergeOut(l).
MergeanytworanklnodesFl,Fliftheydenethesameideal,andtheyhavethesamesetsofoutgoingarcs.
Example3.
7.
ConsiderthepolynomialsetF={x30x0,x0x2x2,x1x2,x22x2,x2x23x3},whoseassociatedgraphisthestargraph(x2isconnectedtox0,x1,x3).
Figure6illustratesasequenceofoperations(triangulation,elimination,andmerge)performedonitsinduced84DIEGOCIFUENTESANDPABLOA.
PARRILOx30x0,x0x2x2,x22x2x1x2,x22x2x22x2,x2x23x30tria==x30x0,x2x01,x21x1x2,x22x2x22x2,x2x23x30elim==x30x0x01x1x2,x22x2x22x2,x2x23x3,x2x22x2,x2x23x3,x210elim==x30x0x01x1x2x22x2,x2x23x3,x2x22x2,x2x23x3,x210tria==x30x0x01x1x2x2,x3x21,x3x21,x310elim==x30x0x01x1x2x2x21x21x3x3x31mergeIn=====mergeOut=====x30x0x01x1x2x2x21x3x310123Figure6.
ChordaltriangularizationfromExample3.
7.
chordalnetwork.
Thechordalnetworkobtainedhasthreechains:(x30x0,x1x2,x2,x3),(x01,x1x2,x21,x3),(x01,x1x2,x21,x31).
ThesechainsgiveatriangulardecompositionofF.
Algorithm1presentsthechordaltriangularizationmethod.
Theinputconsistsofapoly-nomialsetFK[X]andachordalgraphG.
Asintheaboveexample,theoutputofthealgorithmisalwaysatriangularchordalnetwork,anditencodesatriangulardecompositionofthegivenpolynomialsetF.
3.
3.
Algorithmanalysis.
Theobjectiveofthissectionistoprovethat,whentheinputFischordallyzero-dimensional(Denition3.
1),Algorithm1producesaG-chordalnetwork,whosechainsgiveatriangulardecompositionofF.
Asdescribedbelow,thechordallyzero-dimensionalassumptionisonlyneededinorderforthealgorithmtobewelldened(recallthatuptothispointwehaveonlydenedtriangulardecompositionsofzero-dimensionalsystems).
LaterinthepaperwewillseehowtoextendAlgorithm1toarbitraryideals.
Denition3.
8.
LetNbeachordalnetwork,andletC=(F0,Fn1)beachain.
ThevarietyofthechainisV(C):=V(F0Fn1).
ThevarietyV(N)ofthechordalnetworkistheunionofV(C)overallchainsC.
Theorem3.
9.
LetFK[X],supportedonchordalgraphG,bechordallyzero-dimensional.
Algorithm1computesaG-chordalnetworkwhosechainsgiveatriangulardecompositionofF.
CHORDALNETWORKSOFPOLYNOMIALIDEALS85Algorithm1ChordaltriangularizationInput:PolynomialsetFK[X]supportedonachordalgraphGOutput:TriangularG-chordalnetworkNsuchthatV(N)=V(F)1:procedureChordalNet(F,G)2:N:=inducedG-chordalnetworkofF3:forl=0:n1do4:forFlnodeofNofrankldo5:Triangulate(Fl)6:MergeOut(l)7:iflinate(T)11:MergeOut(p)12:MergeIn(l)13:returnNWewillsplittheproofofTheorem3.
9intoseverallemmas.
Werstshowthatthealgorithmiswelldened;i.
e.
,weonlyperformtriangulationoperations(line5)onnodesFlthatdenezero-dimensionalideals.
Lemma3.
10.
LetFK[X]bechordallyzero-dimensional.
TheninAlgorithm1everytriangulationoperationisperformedonazero-dimensionalideal.
Proof.
SeeAppendixA.
1.
Wenowshowthatthechordalstructureispreservedduringthealgorithm.
Lemma3.
11.
LetNbeaG-chordalnetwork.
ThentheresultofperformingatriangulationoreliminationoperationisalsoaG-chordalnetwork.
Proof.
Considerrstatriangulationoperation.
NotethatifFlK[Xl],theneachTinatriangulardecompositionisalsoinK[Xl].
Considernowaneliminationoperation.
LetTK[Xl]andFpK[Xp]betwoadjacentnodes.
UsingLemma2.
6,elimp(T)K[Xl\{xl}]K[Xp].
Thus,thenewnodeFp:=Fp∪elimp(T)K[Xp].
ItisclearthatforbothoperationsthelayeredstructureofNispreserved(i.
e.
,arcsfollowtheeliminationtree).
Wenextshowthatthechainsoftheoutputnetworkaretriangularsets.
Lemma3.
12.
TheoutputofAlgorithm1isatriangularG-chordalnetwork.
Proof.
LetTK[Xl]bearanklnodeforwhichwewillperformaneliminationopera-tion.
NotethatTmustbetriangularaswepreviouslyperformedatriangulationoperation.
Therefore,thereisauniquepolynomialf∈Twithmvar(f)=xl.
WhenweperformtheeliminationoperationthisistheonlypolynomialofTwekeep,whichconcludestheproof.
Finally,weshowthatthevarietyispreservedduringthealgorithm.
86DIEGOCIFUENTESANDPABLOA.
PARRILOLemma3.
13.
LetNbetheoutputofAlgorithm1.
ThenV(N)=V(F),andmoreover,anytwochainsofNhavedisjointvarieties.
Proof.
Letusshowthatthevarietyispreservedwhenweperformtriangulation,elimina-tion,andmergeoperations.
First,notethatamergeoperationdoesnotchangethesetofchainsofthenetwork,sothevarietyispreserved.
Considernowthecaseofatriangulationoperation.
LetNbeachordalnetwork,andletFbeoneofitsnodes.
LetTbeatriangulardecompositionofF,andletNbethechordalnetworkobtainedafterreplacingFwithT.
LetCbeachainofNcontainingF,andletC=C\{F}.
ThenV(C)=V(C)∩V(F)=V(C)∩T∈TV(T)=T∈TV(C)∩V(T)=T∈TV(C∪{T}).
NotethatC∪{T}isachainofN.
Moreover,allchainsofNthatcontainoneofthenodesofThavethisform.
Thus,thetriangulationstepindeedpreservesthevariety.
Finally,considerthecaseofaneliminationoperation.
LetTK[Xl]beanode,let(T,Fp)beanarc,andletFp=Fp∪elimp(T),Tl=T\elimp(T).
LetNbethenetworkobtainedafteraneliminationsteponT.
ItisclearthatV(T∪Fp)=V(Tl∪elimp(T)∪Fp)=V(Tl∪Fp).
SinceachaininNcontainingT,FpturnsintoachaininNcontainingTl,Fp,weconcludethattheeliminationstepalsopreservesthevariety.
ProofofTheorem3.
9.
Wealreadyprovedthetheorem,sinceweshowedthatthealgorithmiswelldened(Lemma3.
10),chordalstructureispreserved(Lemma3.
11),andthechainsintheoutputaretriangularsets(Lemma3.
12)thatdecomposethegivenvariety(Lemma3.
13).
3.
4.
Radicalandirreducibledecompositions.
WejustshowedthatAlgorithm1cancom-putechordalnetworkrepresentationsofsomezero-dimensionalproblems.
However,wesome-timesrequireadditionalpropertiesofthechordalnetwork.
Inparticular,insection4wewillneedsquare-freerepresentations,i.
e.
,suchthatanychaingeneratesaradicalideal.
Asshownnext,wecanobtainsuchrepresentationsbymakingonechangeinAlgorithm1:wheneverweperformatriangulationoperation,weshouldproduceasquare-freedecomposition.
Proposition3.
14.
AssumethatalltriangulardecompositionscomputedinAlgorithm1aresquare-free.
Thenanychainoftheoutputnetworkgeneratesaradicalideal.
Proof.
SeeAppendixA.
1.
Insteadofradicality,wecouldfurtheraskforanirreduciblerepresentation,i.
e.
,suchthatanychaingeneratesaprimeideal.
Theobviousmodicationtomakeistorequirealltriangulationoperationstoproduceirreducibledecompositions.
Unfortunately,thisdoesnotalwayswork.
Indeed,wecanndirreducibleunivariatepolynomialsfK[x0],gK[x1]suchthatf,gK[x0,x1]isnotprime(e.
g.
,f=x20+1,g=x21+1).
Nonetheless,thereisanadvantageofmaintainingprimeidealsthroughthealgorithm:itgivesasimpleboundonthesizeofthetriangularnetworkcomputed,asshownnext.
Thisboundwillbeusedwhenanalyzingthecomplexityofthealgorithm.
CHORDALNETWORKSOFPOLYNOMIALIDEALS87Lemma3.
15.
AssumethatalltriangulardecompositionscomputedinAlgorithm1areir-reducible.
Thenthenumberofranklnodesintheoutputisatmost|V(F∩K[Xl])|.
Proof.
Letusseethatthereareatmost|V(F∩K[Xl])|ranklnodesafterthemergeoperationfromline6.
Firstnotethatwhenweperformthisoperationanyranklnodehasanoutgoingarctoallrankpnodes(wherexpistheparentofxl).
Therefore,thisoperationmergesanytworanklnodesthatdenethesameideal.
Sincetheseidealsareallmaximal,thenforanytwodistinctnodesTl,TlwemusthaveV(Tl)∩V(Tl)=.
AlsonotethatbothV(Tl),V(Tl)aresubsetsofV(F∩K[Xl]).
Thelemmafollows.
Remark3.
16.
Thereareotherwaystoachievetheaboveboundthatdonotrequirecom-putingirreducibledecompositions.
Forinstance,wecanforcethevarietiesV(Tl),V(Tl)tobedisjointbyusingidealsaturation.
3.
5.
Complexity.
WeproceedtoestimatethecostofAlgorithm1inthechordallyzero-dimensionalcase.
Wewillshowthatthecomplexity2isO(nqO(κ)),whereκisthetreewidth(orcliquenumber)ofthegraph,andqisacertaindegreeboundonthepolynomialsthatweformalizebelow.
Inparticular,whenthetreewidthκisbounded,thecomplexityislinearinnandpolynomialinthedegreeboundq.
Denition3.
17(q-domination).
WesaythatapolynomialsetFlK[Xl]isq-dominatedifforeachxi∈Xlthereissomef∈Flsuchthatmvar(f)=xi,init(f)=1,anddeg(f,xi)≤q.
LetFK[X]besupportedonachordalgraphG.
WesaythatFischordallyq-dominatedifF∩K[Xl]isq-dominatedforeachmaximalcliqueXlofgraphG.
Example3.
18.
Thecoloringequationsin(1)arechordallyq-dominatedsincetheequationsxqi1arepresent.
AnotherimportantexampleisthecaseofniteeldsFq,sinceifweincludetheequationsxqixi,asisoftendone,theproblembecomeschordallyq-dominated.
Remark3.
19.
ObservethatifFischordallyq-dominated,thenitisalsochordallyzero-dimensional.
Conversely,ifFischordallyzero-dimensional,thenwecanapplyasimpletransformationtomakeitchordallyq-dominated(forsomeq).
Concretely,foreachmaximalcliqueXlwecanenlargeFwithaGr¨obnerbasisofF∩K[Xl].
Wenotethatwealsousedtheq-dominatedconditionin[9]toanalyzethecomplexityofchordalelimination.
TheimportanceofthisconditionisthatitallowsustoeasilyboundthecomplexityofcomputingGr¨obnerbasesortriangulardecompositions,asstatednext.
Proposition3.
20.
Foranyq-dominatedpolynomialsetonkvariables,thecomplexityofcomputingGr¨obnerbasesand(square-free/irreducible)triangulardecompositionsisqO(k).
Proof.
SeeAppendixA.
1.
Theabovepropositiongivesusthecostofthetriangulationoperations.
However,weneedtoensurethattheseoperationsareindeedperformedonaq-dominatedideal,asshownnext.
Lemma3.
21.
LetFK[X]bechordallyq-dominated.
TheninAlgorithm1anytriangu-lationoperationisperformedonaq-dominatedideal.
Proof.
TheproofisanalogoustothatofLemma3.
10.
2Herethecomplexityismeasuredintermsofthenumberofeldoperations.
88DIEGOCIFUENTESANDPABLOA.
PARRILOWearereadytoestimatethecomplexityofchordaltriangularization.
Fortheanalysisweassumethatthemergeoperationfromline6(resp.
,line11)isperformedsimultaneouslywiththetriangulation(resp.
,elimination)operations;i.
e.
,assoonaswecreateanewnode,wecompareitwiththepreviousnodesofthesameranktocheckifitisrepeated.
Lemma3.
22.
LetFK[X]bechordallyq-dominated.
Assumethatalltriangulardecom-positionscomputedinAlgorithm1areirreducible.
Thenthroughoutthealgorithmthewidthofthenetworkisalwaysboundedbyqκ,independentlyofthenumberofvariables.
Proof.
ThisisaconsequenceofLemma3.
15.
SeeAppendixA.
1.
Remark3.
23(chordalnetworkoflinearsize).
Itfollowsfromthelemmathatforxedq,κ,anychordallyq-dominatedFK[X]oftreewidthκhasachordalnetworkrepresentationwithO(n)nodes.
Theorem3.
24.
LetFK[X]bechordallyq-dominated.
Thecomplexityofchordaltrian-gularizationisO(nWqO(κ)),whereWisaboundonthewidthofthenetworkthroughoutthealgorithm.
Ifalltriangulationoperationsareirreducible,thecomplexityisO(nqO(κ)).
Proof.
FromProposition3.
20andLemma3.
21weknowthateachtriangulationoperationtakesqO(κ),andthusthecostofalltriangulationsisO(nWqO(κ)).
Thecostoftheeliminationoperationsisnegligible.
Asforthemergingoperations,wecanecientlyverifyifanewnodeisrepeatedbyusingahashtable.
Thus,thecostofthemergingoperationisalsonegligible.
Finally,ifalltriangulationoperationsareirreducible,thenW≤qkbecauseofLemma3.
22.
Remark3.
25(beyondchordallyzero-dimensional).
Wewilllaterseethat,afterasuitableredenitionofthetriangulationstep,Algorithm1canalsobeappliedtoarbitraryideals.
Nonetheless,thecomplexityboundsfromabovedodependonthespecialstructureofthechordallyzero-dimensionalcase.
Indeed,solvingpolynomialequationsoftreewidthoneisNP-hard[9,Ex.
1.
1],andcountingtheirnumberofsolutionsisP-hard(eveninthegenericcasefortreewidthtwo[8,Prop.
24]).
Asaconsequence,chordaltriangularizationwillnotalwaysruninpolynomialtime.
WhenusingAlgorithm1insuchhardinstances,wemayendupwithveryhighdegreepolynomialsorwithaverylargenumberofnodes.
4.
Computingwithchordalnetworks.
Triangulardecompositionsareoneofthemostcommontoolsincomputationalalgebraicgeometry.
Thereasonisthattherearemanygoodalgorithmstocomputethemandthattheycanbeusedtoderiveseveralpropertiesoftheunderlyingvariety.
However,asseeninExample1.
1,thesizeofthedecompositionobtainedmightbeextremelylarge(exponential)evenforverysimplecases.
Chordalnetworkscanprovideacompactrepresentationfortheselargedecompositions.
Wewillseehowtoeectivelyusethedatastructureofchordalnetworkstocomputeseveralpropertiesofthevariety.
LetI=Fbeazero-dimensionalideal.
Weconsiderthefollowingproblems.
Elimination.
DescribetheprojectionofV(I)ontothelastnlcoordinates.
Zerocount.
Determinethenumberofsolutions,i.
e.
,thecardinalityofV(I).
Sampling.
SamplerandompointsfromV(I)uniformly.
Radicalmembership.
Determineifapolynomialh∈K[X]vanishesonV(I),or,equiva-lently,determineifh∈√I.
Inthissectionwewilldevelopecientalgorithmsfortheaboveproblems,givenasquare-CHORDALNETWORKSOFPOLYNOMIALIDEALS89freechordalnetworkN(withpossiblyexponentiallymanychains).
RecallthatsuchanetworkcanbeobtainedasexplainedinProposition3.
14.
Wewillseethattherstthreeproblemscanbesolvedrelativelyeasily.
Theradicalmembershipproblemismorecomplicated,andmostofthissectionwillbededicatedtoit.
Wenotethatthealgorithmsforeliminationandradicalmembershipwillnaturallyextendtothepositive-dimensionalcase.
4.
1.
Elimination.
Theeliminationproblemisparticularlysimple,thankstotheelimina-tionpropertyoflexicographicGr¨obnerbases.
ForanarbitrarychordalnetworkN,letN≥ldenotethesubsetofNconsistingofnodesofrankkwithk≥l.
ThenN≥lisachordalnetworkrepresentationoftheprojectionofV(I)ontothelastnlcoordinates.
4.
2.
Countingsolutions.
Wewanttodetermine|V(N)|forasquare-freechordalnet-workN.
Recallfrom(3)that|V(T)|=deg(T)forasquare-freetriangularsetT.
Therefore,wejustneedtocomputethesumofdeg(C)overallchainsCofthenetwork.
Wecandothisecientlyviadynamicprogramming,asexplainedinthefollowingexample.
Example4.
1(zerocount).
Letusdetermine|V(N)|forthechordalnetworkfromFigure5,whichcorrespondstocounting4-coloringsfortheblue/solidgraphfromFigure4a.
Foraranklnodeflofthenetwork,letitsweightw(fl)beitsdegreeinxl.
ThenwejustneedtocomputeCfl∈Cw(fl)wherethesumisoverallchainsofthenetwork.
Wecandothisecientlybysuccessivelyeliminatingthenodesofthenetwork.
Letusrsteliminatethenodesofrank0.
Letfa0,fb0bethetwonodesofrank0,withweightsw(fa0)=3,w(fb0)=2.
Letfa6,fb6,fc6bethenodesofrank6,withweightsw(fa6)=w(fc6)=1,w(fb6)=2.
Notethatanychaincontainingfa6mustalsocontainfa0.
Therefore,wecanremovethearc(fa0,fa6)andupdatetheweightw(fa6)=1*3.
Similarly,anychaincontainingfb6(orfc6)mustalsocontainfb0.
Sowemaydeletethearcs(fb0,fb6)and(fb0,fc6)andupdatetheweightsw(fb6)=2*2,w(fc6)=1*2.
Bydoingthis,wehavedisconnected,oreliminated,allnodesofrank0.
Continuingthisprocedure,thenalweightsobtainedforeachrankareshownbelow.
Thenumberofsolutionsisthelastnumbercomputed:10968.
rk(0)→[3,2],rk(1)→[3,2],rk(2)→[3,2],rk(3)→[3,2,4],rk(4)→[3,2,4],rk(5)→[50,25,20,20,16],rk(6)→[3,4,2],rk(7)→[264,650],rk(8)→[2742],rk(9)→[10968].
Algorithm2generalizestheaboveexampletoarbitrarychordalnetworks.
ThecomplexityisO(nW2),sinceweperformoneoperationforeacharcofthenetwork.
4.
3.
Samplingsolutions.
UniformlysamplingsolutionscanbedonequiteeasilybyusingthepartialrootcountscomputedinAlgorithm2.
Insteadofgivingaformaldescriptionwesimplyillustratetheprocedurewithanexample.
Example4.
2(sampling).
ConsideragainthechordalnetworkofFigure5.
Wewanttouniformlysampleapoint(x0,x9)fromitsvariety,andwefollowabottom-upstrategy.
Letusrstchoosethevaluex9.
Sincethereisauniquerank9nodef9=x491,thenx9mustbeoneofitsfourroots.
Notethateachoftheserootsextendsto2742solutions(afourthofthetotalnumberofsolutions).
Therefore,x9shouldbeequallylikelytobeanyoftheseroots.
Giventhevalueofx9,wecannowsetx8tobeanyofthethreerootsof90DIEGOCIFUENTESANDPABLOA.
PARRILOAlgorithm2CountsolutionsInput:ChordalnetworkN(triangular,squarefree)Output:CardinalityofV(N)1:procedureZeroCount(N)2:forfnodeofNdo3:w(f):=(mdeg(f)ifxrk(f)isaleafelse0)4:forl=0:n1do5:for(fl,fp)arcofNwithrk(fl)=ldo6:w(fp):=w(fp)+w(fl)mdeg(fp)7:returnsumofw(fn1)overallnodesofrankn1f8=x38+x28x9+x8x29+x39,eachequallylikely.
Considernowthetworank7nodesfa7,fb7ofdegrees1and2.
Notethatx7shouldbeeitherarootoffa7orarootoffb7(forthegivenvaluesofx8,x9).
Inordertosampleuniformly,weneedtoknowthenumberofsolutionsthateachofthosevaluesextendsto.
FromExample4.
1weknowthatfa7leadsto264pointsonthevariety,andfb7leadsto650.
Therefore,wecandecidewhichofthemtousebasedonthoseweights.
Assumingwechoosefb7,wecannowsetx7tobeanyofitstworoots,eachequallylikely.
Itisclearhowtocontinue.
4.
4.
Radicalmembership.
Intheradicalidealmembershipproblemwewanttocheckwhetherh∈K[X]vanishesonV(N).
ThisisequivalenttodeterminingwhetherforeachchainCofNthenormalformhC:=hmodCisidenticallyzero.
WewillproposeaMonteCarloalgorithmtoecientlytestthisproperty(withoutiteratingoverallchains)undercertainstructuralassumptionsonthepolynomialh.
Ourmainresultisthefollowing.
Theorem4.
3(radicalmembership).
LetFK[X]bechordallyq-dominated.
LetNbeachordalnetworkrepresentationofFofwidthW.
Lethbeapolynomialthatdecomposesash=lhlwithhlK[Xl].
ThereisaMonteCarloalgorithmthatdetermineswhetherhvanishesonV(F)inO(nWq2κ+nW2qκ).
HerethenotationOignorespolynomialfactorsinthecliquenumberκ.
Remark4.
4.
Thetheoremisrestrictedtopolynomialshthatpreservesomeofthestruc-tureofthegraphG,althoughtheymayinvolveallthevariablesintheringK[X](asopposedtothepolynomialsofthechordalnetwork).
Theabove-mentionedMonteCarloalgorithmalsoworksforothertypesofpolynomialsh,butwedonotprovecomplexityboundsforthem.
Wepointoutthattheabovecomplexityresultisfarfromtrivial.
TojustifythisclaimwecanshowthatasimplevariationoftheradicalmembershipproblemisNP-hardunderverymildassumptions.
Example4.
5(zerodivisorproblem).
Considerthezerodivisorproblem:determineifapolynomialh∈K[X]vanishesonatleastonepointofV(I).
AlsoconsidertheNP-completesubsetsumproblem:decideifasetofintegersA={a0,an1}containsasubsetwhosesumissomegivenvalueS.
WecanreduceittothezerodivisorproblembyconsideringtheidealI:=xi(xiai):0≤iinducedchordalnetworkisalreadytriangular(W=1,q=2).
Weproceedtoderiveourradicalidealmembershiptest.
Wewillinitiallyassumethatthevariablesofhareallcontainedinapathoftheeliminationtree.
Later,wewillextendthealgorithmtopolynomialshthatdecomposeintomultiplepathsoftheeliminationtree.
Finally,wewillprovethecomplexityboundfromTheorem4.
3.
Membershiponapath.
ConsiderthecasewheretheeliminationtreeofthegraphGisapath(i.
e.
,ithasonlyoneleaf).
Alternatively,wecanassumethatallthevariablesofharecontainedinapathoftheeliminationtree.
Asbefore,lethC:=hmodCdenotethenormalformwithrespecttochainC.
Ourradicalidealmembershiptestisbasedontwosimpleideas.
First,wewillcheckwhetherthepolynomialH(X):=CrChC(X)isidenticallyzeroforsomerandomcoecientsrC∈K.
Clearly,forsucientlygenericvaluesofrC,thepolynomialH(X)willbezeroifandonlyifeachhCiszero.
ThesecondideaisthatweevaluateH(X)insomerandompointsxi∈K.
Thus,wejustneedtocheckwhetherthescalarH(X)∈Kiszero.
Weillustratehowthealgorithmworksthroughthefollowingexample.
Example4.
6(radicalmembership).
ConsideragainthechordalnetworkofFigure5.
Letusverifythatthepolynomialh(x)fromFigure7vanishesonitsvariety.
Weneedtoshowthatthereduction(normalform)ofhbyeachchainofthenetworkiszero.
Asinthecaseofcountingsolutions,wewillachievethisbysuccessivelyeliminatingnodes.
Notethatthevariablesofhare{x0,x6,x7,x8,x9},whichcorrespondtoapathoftheeliminationtree.
Thus,werestrictourselvestothepartofthenetworkgivenbythesevariables,asshowninFigure7.
h(x)=x20x6x20x7x0x6x8x0x6x9x0x27x0x28x0x8x9x0x29+x6x8x9x37+x28x9+x8x29x30+x20x7+x0x27+x37x20+x0x6+x0x7+x26+x6x7+x27x6x7x26+x6x8+x6x9+x28+x8x9+x29x6+x7+x8+x9x7x9x27+x7x8+x7x9+x28+x8x9+x29x38+x28x9+x8x29+x39x491h(x)h(x)1·ha01·hb01·hb012·ha61·hb612·hc612·ha712·hb71·h8h9=006789Figure7.
SketchoftheradicalidealmembershiptestfromExample4.
6.
Letusstartbyprocessingthetwonodesofrank0.
Wehavetocomputethereductionofh(x)moduloeachofthesenodes.
Afterward,wewillsubstitutex0inthesereducedpolyno-mialswitharandomvalueonK;inthiscasewechoosex0=1.
Letha0,hb0bethepolynomialsobtainedafterthereductionandsubstitution,asshowninFigure7.
Thesetwopolynomialswillbesenttotheadjacentrank6nodes.
92DIEGOCIFUENTESANDPABLOA.
PARRILOConsidernowarankpnodefpthatreceivescertainpolynomialsfromitsadjacentranklnodes.
Wenowperformarandomlinearcombinationoftheseincomingpolynomials,thenwereducethislinearcombinationmodulofp,andnallywesubstitutexpwitharandomvaluexp.
Forthisexamplethelinearcombinationwillbeanaverage,andtherandompointsxpwillbe1.
Figure7indicatesthepolynomialsreceivedandoutputbyeachnode.
Forinstance,h8isobtainedbyreducing12(ha7+hb7)modulof8=x38+x28x9+x8x29+x39andthenplugginginx8=1.
Thepolynomialsobtainedwiththisprocedureareshownbelow.
Notethatthelastpolynomialcomputediszero,agreeingwiththefactthath(x)vanishesonthevariety.
ha0=x6x8x9x6x8x6x9+x6x37x27x7+x28x9x28+x8x29x8x9x29,hb0=x36x26+x6x8x9x6x8x6x9+x28x9x28+x8x29x8x9x29,ha6=x37x27+x7x8x9x7x8x7x9+x28x9x28+x8x29x8x9x29,hb6=x38x28x9x8x29x39,hc6=x37+x27(3x8+3x91)+x7(3x28+5x8x9x8+3x29x9)+x38+3x28x9x28+3x8x29x8x9+x39x29,ha7=hb7=x38x28x9x8x29x39,h8=h9=0.
Algorithm3generalizestheprocedurefromtheaboveexample.
ObservingthateachnodeflofthenetworkhasanassociatedpolynomialH(fl),whichisrstreducedmodulofl,thenwesubstitutethevaluexlandnallywepassthispolynomialtotheadjacentnodes.
Alsonotethatwechooseonerandomscalarxlforeachvariable,andonerandomscalarrlpforeacharcofthenetwork.
Algorithm3RadicalidealmembershipInput:ChordalnetworkN(triangular,square-free)andpolynomialh(x)suchthatallitsvariablesarecontainedinapathoftheeliminationtree.
Output:True,ifhvanishesonV(N).
False,otherwise.
1:procedureRIdealMembership(N,h)2:xm:=mvar(h)3:forfnodeofNdo4:H(f):=(hifrk(f)=melse0)5:forl=0:n1do6:xl:=randomscalar7:forflnodeofNofrankldo8:H(fl):=H(fl)modfl9:pluginxlinH(fl)10:for(fl,fp)arcofNdo11:rlp:=randomscalar12:H(fp):=H(fp)+rlpH(fl)13:return(TrueifH(fn1)=0forallrankn1nodeselseFalse)Correctness.
WeproceedtoshowthecorrectnessofAlgorithm3.
Wewillneedaprelim-inarylemmaandsomenewnotation.
Foranyl,letXldenotethesubtreeoftheeliminationCHORDALNETWORKSOFPOLYNOMIALIDEALS93treeconsistingofxlandallitsdescendants(e.
g.
,Xn1consistsofallvariables).
Foraranklnodeflofthenetwork,wewillsaythatanfl-subchainClisthesubsetofachainC,withfl∈C,restrictedtonodesofrankiforsomexi∈Xl.
Lemma4.
7.
LetNbeachordalnetworkwhoseeliminationtreeisapath,andleth∈K[X].
LetflbearanklnodeofN.
InAlgorithm3,thenalvalueofH(fl)isgivenbyplugginginthevaluesx1x2,xlinthepolynomialClrClhmodCl,wherethesumisoverallfl-subchainsCl,andwhererCldenotestheproductoftherandomscalarsrijalongthesubchainCl.
Proof.
SeeAppendixA.
2.
Theorem4.
8.
LetNbeachordalnetwork,triangularandsquare-free,andletqbeaboundonthemaindegreesofitsnodes.
Leth∈K[X]besuchthatallitsvariablesarecontainedinapathoftheeliminationtree.
Algorithm3behavesasfollows:IfhvanishesonV(N),italwaysreturns"True.
"Ifnot,itreturns"False"withprobabilityatleast1/2,assumingthattherandomscalarsrlp,xlarechosen(independent,uniformlydistributed)fromsomesetSKwith|S|≥2nq.
Proof.
DenotinghC:=hmodC,Lemma4.
7tellsusthatAlgorithm3checkswhetherCrChC(X)=0,whererCistheproductofallscalarsrlpalongthechainC.
IfhvanishesonV(N),theneachhCiszeroandthusthealgorithmreturns"True.
"AssumenowthathdoesnotvanishonV(N),andthusatleastonehCisnonzero.
LetRbethesetofallrandomscalarsrlpusedinthealgorithm,whichwenowseeasvariables.
ConsiderthepolynomialH(X,R):=CrC(R)hC(X),andnotethatitisnonzero.
ObservethatthedegreeofH(X,R)isatmostnq,sincedeg(rC)≤nanddeg(hC)≤n(q1).
UsingtheSchwartz–Zippellemma(see,e.
g.
,[34,section6.
9]),theprobabilitythatHevaluatestozeroforrandomvaluesrlp,xl∈Sisatmostnq/|S|≤1/2.
Remark4.
9.
TheabovetheoremrequiresthatKcontainsucientlymanyelements.
Ifnecessary,wemayconsideraeldextensionLKandperformallcomputationsoverL[X].
Combiningmultiplepaths.
WenowextendAlgorithm3toworkforotherpolynomialsh.
Specically,weassumethatthepolynomialcanbewrittenash=ihi,wherethevariablesofeachhibelongtoapathoftheeliminationtree.
Weletxmi:=mvar(hi)denotethemainvariables,andwecanassumethattheyarealldistinct.
WeonlyneedtomaketwosimplemodicationstoAlgorithm3.
(i)Previously,weinitializedthealgorithmwithnonzerovaluesinasinglerank(seeline4).
Wenowinitializethealgorithminmultipleranks:H(fmi)=hiifrk(fmi)=mi.
(ii)Whencombiningtheincomingpolynomialstoanodefp,wenowtakearandomanecombination(i.
e.
,lrlpH(fl)forsomescalarsrlpsuchthatlrlp=1).
Notethatin94DIEGOCIFUENTESANDPABLOA.
PARRILOtheexamplefromFigure7wetooktheaverageoftheincomingnodes,sothisconditionissatised.
Therstmodicationisquitenaturalgiventhedecompositionofthepolynomialh.
Theseconditemislessintuitive,butitissimplyanormalizationtoensurethatallpolynomialshiarescaledinthesamemanner.
ThecorrectnessofthismodiedalgorithmfollowsfromthefactthatLemma4.
7remainsvalid,asshownnext.
Lemma4.
10.
LetNbeachordalnetwork,andleth=ihi∈K[X]besuchthatthevari-ablesofeachhiarecontainedinapathoftheeliminationtree.
WiththeabovemodicationstoAlgorithm3,thenalvalueofH(fl)isasstatedinLemma4.
7.
Proof.
SeeAppendixA.
2.
Remark4.
11.
Notethatanyhcanbewrittenash=n1i=0hi,wherehicorrespondstothetermswithmainvariablexi.
Evenwhentheeliminationtreeisapath,itisusuallymoreecienttodecomposeitinthismanneranduseAlgorithm3withtheabovemodications.
Complexity.
WenallyproceedtoprovethecomplexityboundfromTheorem4.
3.
WerestrictourselvestopolynomialshthatpreservethesparsitystructuregivenbythechordalgraphG.
Moreprecisely,weassumethatthevariablesofeachofthetermsofhcorrespondtoacliqueofG,or,equivalently,thath=lhlforsomehl∈K[Xl].
Naturally,wewilluseAlgorithm3withthetwomodicationsfromabove.
ThekeyideatonoticeisthatAlgorithm3preserveschordality,asstatednext.
Lemma4.
12.
AssumethatinAlgorithm3theinitialvaluesofH(fl)aresuchthatH(fl)K[Xl](whererk(fl)=l).
Thenthesameconditionissatisedthroughoutthealgorithm.
Proof.
TheupdateruleusedinAlgorithm3isoftheformH(fp):=H(fp)+rlpφl(hl)forsomehl∈K[Xl],whereφldenotesthefunctionalthatplugsinxl.
UsingLemma2.
6,wehaveφl(hl)K[Xl\{xl}]K[Xp].
Theresultfollows.
ProofofTheorem4.
3.
WeconsiderAlgorithm3withthemodications(i)and(ii)fromabove.
Notethattheq-dominatedconditionallowsustoboundthedegreesofallpolynomialscomputedinAlgorithm3.
Furthermore,sincechordalityispreserved(Lemma4.
12),allpoly-nomialswillhaveatmostqκterms.
Thecomplexityofthealgorithmisdeterminedbythecostofpolynomialdivisionsandpolynomialadditions.
Polynomialadditiontakeslineartimeinthenumberofterms,anditisperformedonceforeacharcofthenetwork.
Thus,theirtotalcostisO(nW2qκ).
Asforpolynomialdivision,hmodfcanbeobtainedinO(|h||f|log|f|),where|·|denotesthenumberofterms[27].
TheirtotalcostisO(nWq2κ),sincethereisoneoperationpernodeofthenetwork.
5.
Monomialideals.
Wealreadyshowedhowtocomputechordalnetworkrepresentationsofsomezero-dimensionalideals.
Beforeproceedingtothegeneralcase,wewillconsiderthespecialclassofmonomialideals.
Recallthatanidealismonomialifitisgeneratedbymonomials.
Monomialidealsmighthavepositivedimension,buttheirspecialstructuremakestheiranalysisparticularlysimple.
AsinExample1.
2,wewillseethatanymonomialidealadmitsacompactchordalnetworkrepresentation.
Wewillalsoshowhowsuchachordalnetworkcanbeeectivelyusedtocomputeitsdimension,itsequidimensionalcomponents,anditsirreduciblecomponents.
ThesemethodswillbelatergeneralizedtoarbitrarypolynomialCHORDALNETWORKSOFPOLYNOMIALIDEALS95ideals.
5.
1.
Chordaltriangularization.
Algorithm1willbeexactlythesameformonomialidealsasinthezero-dimensionalcase.
Theonlydierenceisthatforthetriangulationoperationsweneedtospecifythetypeofdecompositionused,asexplainednow.
WewillsaythatasetofmonomialsTistriangularifitconsistsofvariables,i.
e.
,T={xi1xim}.
Itiswellknownthatamonomialidealisprimeifandonlyifitisgeneratedbyvariables.
Itisalsoknownthattheminimalprimesofamonomialidealarealsomonomial.
ItfollowsthatanymonomialidealIdecomposesasV(I)=TV(T),wheretheunionisoversometriangularmonomialsetsT.
Byusingtheabovedecompositionineachtriangulationoperation,chordaltriangulariza-tioncannowbeappliedtomonomialideals,asestablishedinthepropositionbelow.
Wepointoutthateventhoughthisdecompositionseemsquitedierentfromthatofsection3.
1,botharespecialinstancesofamoregeneraltheorythatwillbediscussedinsection6.
1.
Proposition5.
1.
LetFbeasetofmonomialssupportedonachordalgraphG.
Algorithm1computesaG-chordalnetwork,whosechainsgiveatriangulardecompositionofF.
Proof.
Provingthatthevarietyispreservedinthealgorithmisessentiallythesameasforthechordallyzero-dimensionalcase(Lemma3.
13).
Itisstraightforwardtoseethatthechainsoftheoutputaretriangular(i.
e.
,theyconsistofvariables).
Example5.
2.
ConsidertheidealI=x0x1,x0x2,x0x3,x1x2,x1x4,x2x5,x3x4,x3x5,x4x5.
TheresultofchordaltriangularizationisshownontheleftofFigure8.
0x0x10x1x2x2x20x3x300x4x4x50012345top===dim0x0x10x1x2x2x20x3x300x4x4x50012345Figure8.
ChordalnetworkfromExample5.
2anditstop-dimensionalpart.
Asinthechordallyzero-dimensionalcase,wecanalsoprovethatthecomplexityislinearinnwhenthetreewidthisbounded.
Theorem5.
3.
LetFbeasetofmonomialssupportedonachordalgraphGofcliquenum-berκ.
ThenFcanberepresentedbyatriangularchordalnetworkwithatmostn2κnodes,whichcanbecomputedintimeO(n2O(κ)).
Proof.
Notethatafterthelthtriangulationroundwewillhaveatmost2κranklnodes,sincethetriangularmonomialsetsinK[Xl]areinbijectionwiththesubsetsofXl.
Asimilarargumentprovesthatthewidthofthenetworkisboundedby2κafteraneliminationround,andthusthroughoutthealgorithm.
ThecostofcomputingatriangulardecompositioninK[Xl]ispolynomialin2|Xl|,sincewecansimplyenumerateoverallpossibletriangularmonomial96DIEGOCIFUENTESANDPABLOA.
PARRILOsets.
Thus,thecostofalltriangulationoperationsisO(nW2O(κ))=O(n2O(κ)).
Thecostoftheeliminationandmergingoperationsisnegligible.
5.
2.
Computingwithchordalnetworks.
LetNbeachordalnetworkrepresentationofamonomialidealI.
WewillshowhowtoeectivelyuseNtosolvethefollowingproblems:Dimension.
DeterminethedimensionofI.
Top-dimensionalpart.
Describethetop-dimensionalpartofV(I).
Irreduciblecomponents.
DeterminetheminimalprimesofI.
Theaboveproblemscanbeshowntobehardingeneralbyusingthecorrespondencebetweenminimalvertexcoversofagraphandtheirreduciblecomponentsofitsedgeideal(seeExam-ple1.
2).
Wewillseethat,giventhechordalnetwork,thersttwoproblemscanbesolvedinlineartimewithadynamicprogram.
Thethirdoneismuchmorecomplicated,sinceweneedtoenumerateoverallchainsofthenetworktoverifyiftheyareminimal.
Inordertodothiseciently,wewillneedtoaddressthefollowingproblems.
Dimensioncount.
ClassifythenumberofchainsCofNaccordingtoitsdimension.
Isolatedimensiond.
EnumerateallchainsCofNsuchthatdim(V(C))=d.
Weproceedtosolveeachoftheproblemsfromabove.
Tosimplifytheexposition,wewillassumeforthissectionthattheeliminationtreeisapath,butitisnotdiculttoseethatallthesemethodswillworkforarbitrarychordalnetworks.
Dimension.
LetusseethatitisquiteeasytocomputethedimensionofV(N).
SincethevarietyV(T)ofatriangularmonomialsetisalinearspace,itsdimensionisdim(V(T))=n|T|.
Therefore,dim(V(N))=nminC|C|,wheretheminimumistakenoverallchainsofthenetwork.
NotethatweignorethezeroentriesofC.
Inparticular,forthenetworkinFigure8wehavedim(V(N))=64=2.
WereducedtheproblemtocomputingthesmallestcardinalityofachainofN.
Thiscanbedoneusingasimpledynamicprogram,whichisquitesimilartothatinAlgorithm2.
Foreachnodeflwesavethevalue(fl)correspondingtothelengthoftheshortestchainuptolevell.
Foranarc(fl,fp)withfp=0,theupdateruleissimply(fp):=min((fp),1+(fl)).
ItfollowsthatwecancomputeinlineartimethedimensionofV(N).
Top-dimensionalpart.
WecangetachordalnetworkNtopdescribingitstop-dimensionalpartbymodifyingtheprocedurethatcomputesthedimension.
Indeed,assumethatforsomearc(fl,fp)wehave(fp)in((fp),1+(fl))isnotneeded.
Thismeansthatthearc(fl,fp)isunnecessaryforthetop-dimensionalcomponent.
BypruningthearcsofNinsuchamanner,weobtainthewantednetworkNtop.
Example5.
4.
LetNbethenetworkontheleftofFigure8.
NotethatNhasninechains;twoofthemareC1=(x1,x2,x3,x5),C2=(x0,x1,x2,x3,x5),ofdimensions2and1.
Bypruningsomearcs,weobtainitshighestdimensionalpartNtop,shownontherightofFigure8.
ThisnetworkNtoponlyhassixchains;notethatC2isnotoneofthem.
Inthiscaseneitherofthechainsremovedwasminimal(e.
g.
,C2C1),sothatV(N)=V(Ntop).
Thus,bothNandNtoparevalidchordalnetworkrepresentationsoftheidealfromExample5.
2,althoughthelatterispreferredsinceallitschainsareminimal.
Similarly,thenetworkfromFigure2wasobtainedbyusingchordaltriangularizationandthencomputingitshighestdimensionalpart.
CHORDALNETWORKSOFPOLYNOMIALIDEALS97Irreduciblecomponents.
Chordaltriangularizationcanalsoaidincomputingtheminimalprimesofanideal(geometrically,theirreduciblecomponents).
Inthemonomialcase,anychainofNdenesaprimeideal,andthusweonlyneedtodeterminewhichchainsareminimalwithrespecttocontainment.
Insomecasesitisenoughtoprunecertainarcsofthenetwork(e.
g.
,Figure8),butthisisnotalwayspossible.
Unfortunately,wedonotknowabetterprocedurethansimplyiteratingoverallchainsofthenetwork,checkingforminimality.
Nonetheless,wecanmakethismethodmuchmoreeectivebyproceedinginorderofdecreasingdimension.
Thissimpleprocedureisparticularlyecientwhenweareonlyinterestedintheminimalprimesofhighdimension,aswillbeseeninsection7.
1.
Intheremainderofthesectionwewillexplainhowtoenumeratethechainsbydecreasingdimension(thisispreciselythedimensionisolationproblem).
Dimensioncount.
Classifyingthenumberofchainsaccordingtoitsdimensioncanbedonewithadynamicprogramverysimilartothatusedforcomputingthedimension.
Asdiscussedabove,thedimensionofachainissimplygivenbyitscardinality.
Foraranklnodeflofthenetworkandforany0≤k≤l+1,letck(fl)denotethenumberofchainsofthenetwork(uptolevell)withcardinalityexactlyk.
Thenforanarc(fl,fp)withfp=0theupdateruleissimplyck(fp):=ck(fp)+ck1(fl).
Dimensionisolation.
ForsimplicityofexpositionweonlydescribehowtoproduceonechainCofdimensiond,butitisstraightforwardtothengenerateallofthem.
AsinExam-ple4.
2,wefollowabottom-upstrategy,successivelyaddingnodestothechain.
Werstneedtochoosearankn1nodefn1thatbelongstoatleastonechainofdimensiond.
Usingthevaluesck(fl)fromabove,wecanchooseanyfn1forwhichcnd(fn1)≥1.
Assumingthatwechosesomefn1=0,wenowneedtondanadjacentrankn2nodefn2suchthatcnd1(fn2)≥1.
Itisclearhowtocontinue.
6.
Thegeneralcase.
Wenallyproceedtocomputechordalnetworkrepresentationsofarbitrarypolynomialideals.
Wewillalsoseehowthedierentchordalnetworkalgorithmsdevelopedearlier(e.
g.
,radicalidealmembership,isolatingthetop-dimensionalcomponent)haveanaturalextensiontothisgeneralsetting.
6.
1.
Regularchains.
Thetheoryoftriangularsetsforpositive-dimensionalvarietiesismoreinvolved;wereferthereaderto[17,36]foranintroduction.
Wenowpresenttheconceptofregularchains,whichisatthecenterofthistheory.
AsetofpolynomialsTK[X]\Kisatriangularsetifitselementshavedistinctmainvariables.
Lethbetheproductoftheinitials(Denition3.
3)ofthepolynomialsinT.
ThegeometricobjectassociatedtoTisthequasi-componentW(T):=V(T)\V(h)Kn.
Theattachedalgebraicobjectisthesaturatedidealsat(T):=T:h∞={f∈K[X]:hNf∈TforsomeN∈N}.
NotethatV(sat(T))=W(T),wheretheclosureisintheZariskitopology.
98DIEGOCIFUENTESANDPABLOA.
PARRILOPolynomialpseudodivisionisabasicoperationintriangularsets.
Letf,gbepolynomialsofdegreesd,einx:=mvar(g).
Thebasicideaistoseef,gasunivariatepolynomialsinx(withcoecientsinK[X\{x}]),andinorderthatwecanalwaysdividefbyg,werstmultiplybysomepowerofinit(g).
Formally,thepseudoremainderoffbygisprem(f,g):=fifdinit(g)de+1fmod(g).
Pseudodivisioncanbeextendedtotriangularsetsinthenaturalway.
ThepseudoremainderoffbyT={t1,tk},wheremvar(t1)mvar(tk),isprem(f,T)=prem(···(prem(f,t1)tk).
Denition6.
1.
AregularchainisatriangularsetTsuchthatforanypolynomialff∈sat(T)prem(f,T)=0.
Remark6.
2.
Notethatazero-dimensionaltriangularset(Denition3.
3)isaregularchain,sincepseudoreductioncoincideswithGr¨obnerbasesreduction.
Regularchainshaveverynicealgorithmicproperties.
Inparticular,theyarealwayscon-sistent(i.
e.
,W(T)=0),andfurthermoredim(W(T))=n|T|.
Table1summarizessomeoftheseproperties,comparingthemwithGr¨obnerbases.
Table1Gr¨obnerbasesversusregularchains.
Gr¨obnerbasis(G)Regularchain(T)GeometricobjectV(G)W(T)AlgebraicobjectGsat(T)Feasibleif1/∈GalwaysIdealmembershipremainder=0pseudoremainder=0DimensionfromHilbertseriesn|T|EliminationidealGlex∩K[xl,xn1]T∩K[xl,xn1]Denition6.
3.
AtriangulardecompositionofapolynomialsetFisacollectionTofreg-ularchains,suchthatV(F)=T∈TW(T).
Remark6.
4.
Thereisaweakernotionofdecompositionthatiscommonlyused:TisaKalkbrenertriangulardecompositionifV(F)=T∈TW(T).
Example6.
5.
LetF={x0x3x1x2,x2x5x3x4,x4x7x5x6}consistoftheadjacentminorsofa2*4matrix.
Itcanbedecomposedintoeightregularchains:(x0x3x1x2,x2x5x3x4,x4x7x5x6),(x0x3x1x2,x4,x5),(x2,x3,x4x7x5x6),(x1,x3,x4,x5),(x1,x3,x5,x7),(x2,x3,x5,x7),(x2,x3,x6,x7),(x0x3x1x2,x2x5x3x4,x6,x7).
Notethattherstthreetriangularsets(rstline)havedimension83=5.
Observethatthequasi-componentsW(T)ofthesethreesetsdonotcoverthepointsforwhichx3=x7=0,whichiswhyweneedtheremainingvesets.
However,thesethreetriangularsetsalonegiveaKalkbrenerdecompositionofthevariety.
CHORDALNETWORKSOFPOLYNOMIALIDEALS996.
2.
Regularsystems.
Inthestudyoftriangularsets,itisusefultoconsidersystemsofpolynomialscontainingbothequations{fi(x)=0}iandinequations{hj(x)=0}j.
Followingthenotationof[36],wesaythatapolynomialsystemF=(F,H)isapairofpolynomialsetsF,HK[X],anditsassociatedgeometricobjectisthequasi-varietyZ(F):={x∈Kn:f(x)=0forf∈F,h(x)=0forh∈H}.
Forinstance,thequasi-componentW(T)ofatriangularsetisthequasi-varietyofthepoly-nomialsystem(T,init(T)),whereinit(T)isthesetofinitialsofT.
ForapolynomialsystemF=(F,H)wedenotebyelimp(F)thepolynomialsystem(elimp(F),elimp(H)).
WealsodenotebyF1+F2theconcatenationoftwopolynomialsystems,i.
e.
,(F1,H1)+(F2,H2):=(F1∪F2,H1∪H2).
Denition6.
6.
AregularsystemisapairT=(T,U)suchthatTistriangularandforany0≤kinghold:(i)EitherTk=orUk=,wherethesuperscriptkdenotesthepolynomialswithmainvariablexk.
(ii)init(f)(xk+1)=0foranyf∈Tk∪Ukandxk+1∈Z(elimk+1(T))Knk1.
Aregularsystemissquare-freeifthepolynomialsf(xk,xk+1)K[xk]aresquare-freeforanyf∈Tk∪Ukandanyxk+1∈Z(elimk+1(T))Knk1.
Foraregularsystem(T,U)thesetTisaregularchain,and,conversely,foraregularchainTthereissomeUsuchthat(T,U)isaregularsystem[35].
Wangshowedhowtodecomposeanypolynomialsystemincharacteristiczerointo(square-free)regularsystems[35,36].
Denition6.
7.
AtriangulardecompositionofapolynomialsystemFisacollectionTofregularsystems,suchthatZ(F)=T∈TZ(T).
Remark6.
8(binomialideals).
ConsiderapolynomialsystemF=(F,U)suchthatFconsistsofbinomials(twoterms)andH={xi1xim}consistsofvariables.
WecandecomposeFintoregularsystemsT=(T,U)thatpreservethebinomialstructure.
AssumerstthatH={x0,xn1}containsallvariables.
Equivalently,wearelookingforthezerosetofFonthetorus(K\{0})n.
ItiswellknownthatFcanbeconvertedto(binomial)triangularformTbycomputingtheHermitenormalformofthematrixofexponents[31,section3.
2],andtheinequationsUcorrespondtothenonpivotvariables.
ForanarbitraryH,wecanenumerateoverthechoicesofnonzerovariables.
6.
3.
Chordaltriangularization.
Algorithm1extendstothepositive-dimensionalcaseinthenaturalway,althoughwithoneimportantdierence:thenodesofthechordalnetworkwillbepolynomialsystems,i.
e.
,pairsofpolynomialsets.
Wenowdescribethemodicationsofthemainstepsofthealgorithm:Initialization.
ThenodesoftheinducedG-chordalnetworkarenowoftheformFl=(Fl,Hl),whereFl=F∩K[Xl]andHl=.
Triangulation.
ForanodeFlwedecomposeitintoregularsystemsT,andwereplaceFlwithanodeforeachofthem.
Elimination.
LetFlbetheranklnodewewilleliminate,andletFpbeanadjacentrankpnode.
ThenwecreatearankpnodeFp:=Fp+elimp(Fl).
100DIEGOCIFUENTESANDPABLOA.
PARRILOTermination.
Afteralltriangulation/eliminationoperations,wemayremovetheinequationsfromthenodesofthenetwork,i.
e.
,replaceF=(F,H)withF.
x0x3x1x2x2x5x3x4x4x7x5x6tria==elimx0x3x1x2x10x2x5x3x4/x3x2x5,x3x2,x3x4x7x5x6tria==elimx0x3x1x2x10x2x5x3x4/x30/x3x2,x3x3x4x7x5x6/x5x4,x5x4x7x5x6x4x7,x5tria==x0x3x1x2x10x2x5x3x4/x30/x3x2,x3x3x4x7x5x6/x5x7x6,x7/x5x4,x5x4x7x5x6/x7x5,x7x6,x7term==x0x3x1x2x10x2x5x3x40x2,x3x3x4x7x5x6x6,x7x4,x5x5,x701234-7Figure9.
ChordaltriangularizationfromExample6.
9.
Example6.
9.
Figure9illustratesthechordaltriangularizationalgorithmforthepolyno-mialsetFfromExample6.
5.
ThenodesofthechordalnetworkarepolynomialsystemsF=(F,H),whichwerepresentinthegureas(F/H).
Notethatintheterminationstep,afteralltriangulation/eliminationoperations,weremovetheinequationstosimplifythenet-work.
Thenalnetworkhaseightchains,whichcoincidewiththetriangulardecompositionfromExample6.
5.
Wecannowcomputechordalnetworkrepresentationsofarbitrarysystems.
Theorem6.
10.
LetFK[X]besupportedonachordalgraphG.
Withtheabovemodi-cations,Algorithm1computesaG-chordalnetworkN,whosechainsgiveatriangulardecom-positionofF.
Furthermore,thisdecompositionissquare-freeifalltriangulationoperationsaresquare-free.
Proof.
SeeAppendixA.
3.
Remark6.
11.
Wehavenoticedthatchordaltriangularizationisquiteecientforbinomialideals.
Remark6.
8partlyexplainsthisobservation.
However,wedonotyetknowwhetheritwillalwaysruninpolynomialtimewhenthetreewidthisbounded.
6.
4.
Computingwithchordalnetworks.
Wejustshowedhowtocomputechordalnetworkrepresentationsofarbitrarypolynomialsystems.
Wenowexplainhowtoextendthechordalnetworkalgorithmsfromsection4andsection5.
2tothegeneralcase.
Elimination.
SinceregularchainspossessthesameeliminationpropertyaslexicographicGr¨obnerbases,theapproachfromsection4.
1worksinthesameway.
Radicalidealmembership.
Algorithm3extendstothepositive-dimensionalcasesimplybyreplacingpolynomialdivisionwithpseudodivision.
Notethatwerequireasquare-freechordalnetwork,whichcanbecomputedasexplainedinTheorem6.
10.
CHORDALNETWORKSOFPOLYNOMIALIDEALS101Dimensionandequidimensionalcomponents.
ThedimensionofaregularchainTisn|T|,whichisthesameasforthemonomialcase.
Thus,wecancomputethedimensionasinsection5.
2.
Similarly,wecancomputeachordalnetworkdescribingthehighestdimensionalcomponent,andalsoisolateanygivendimensionofthenetwork.
x0x3x1x20x2x5x3x40x2,x3x4x7x5x6x4,x501234-7Figure10.
Top-dimensionalpartofthechordalnetworkfromFigure9.
Example6.
12.
Figure10showsthehighestdimensionalpartofthechordalnetworkfromFigure9.
Thisnetworkonlyhasthreechains,whichgiveaKalkbrenerdecompositionofthevariety(seeExample6.
5).
Likewise,thechordalnetworkfromFigure3givesaKalkbrenertriangulardecompositionoftheidealofadjacentminorsofa2*7matrix.
Irreduciblecomponents.
Unlikethemonomialcase,thechainsofanarbitrarychordalnetworkNwillnotnecessarilydeneprimeideals(seesection3.
4).
However,insomeinter-estingcasesthiswillbethecase,thankstothefollowingwell-knownproperty.
Theorem6.
13.
LetT={t1,tk}bearegularchain.
Assumethatmdeg(ti)=1for1≤iInparticular,notethatallchainsofthechordalnetworkfromFigure3areofthisform.
Wewillseeinsection7.
3thatthesameholdsforotherfamiliesofideals.
Assumenowthatallchainsofthenetworkdeneaprimeideal.
Aplausiblestrategytocomputeallminimalprimes(oronlythehighdimensionalones)isasfollows:(i)IterateoverallchainsTofthenetworkinorderofdecreasingdimension.
(ii)ForachainC,andaminimalprimeIpreviouslyfound,determinewhetherIsat(C)bycheckingwhetherprem(f,C)=0foreachgeneratorfofI.
(iii)IfI:=sat(C)doesnotcontainanypreviouslyfoundprime,computegeneratorsforIbyusingGr¨obnerbases.
Wehaveanewminimalprime.
7.
Examples.
Weconcludethispaperbyexhibitingsomeexamplesofourmethods.
WeimplementedouralgorithmsinSage[30]usingMaple'slibraryEpsilon[37]fortriangulardecompositions,andSingular[12]forGr¨obnerbases.
Theexperimentsareperformedonani7PCwith3.
40GHz,15.
6GBRAM,runningUbuntu14.
04.
7.
1.
Commutingbirthanddeathideal.
WeconsiderthebinomialidealIn1,.
.
.
,nkfrom[14].
Thisidealmodelsageneralizationoftheone-dimensionalbirth-deathMarkovprocesstohigherdimensionalgrids.
In[14]itisgivenaparametrizationofitstop-dimensionalcomponent,aswellastheprimarydecompositionofsomesmallcases.
In[18]KahleuseshisMacaulay2packageBinomials,specializedinbinomialideals,tocomputeprimarydecompositionsof102DIEGOCIFUENTESANDPABLOA.
PARRILOlargerexamples.
WenowshowhowourmethodscangreatlysurpassKahle'smethodsincomputingtheirreducibledecompositionwhenthetreewidthissmall.
Wefocusonthecaseofatwo-dimensionalgrid:In1,n2=Ui,jRi,j+1Ri,jUi+1,j,Di,j+1Ri,jRi,j+1Di+1,j+1,Di+1,j+1Li+1,jLi+1,j+1Di,j+1,Ui+1,jLi+1,j+1Li+1,jUi,j0≤iWelettheparametern1takevaluesbetween1to100,whilen2iseither1or2.
Table2showsthetimeusedbyAlgorithm1fordierentvaluesofn1,n2.
Observethat,forsmallvaluesofn2,ourmethodscanhandleveryhighvaluesofn1thankstoouruseofchordality.
Forcomparison,wenotethatevenforthecasen1=10,n2=1Singular'sGr¨obnerbasisalgorithm(grevlexorder)didnotterminatewithin20hoursofcomputation.
Similarly,neitherEpsilon[37]norRegularChains[25]wasabletocomputeatriangulardecompositionofI10,1within20hours.
Table2TimerequiredbychordaltriangularizationonidealsIn1,n2.
Noothersoftwarewetried[12,18,25,37]cansolvetheseproblems.
n120406080100n2=10:00:450:02:160:04:030:06:280:09:13n2=20:36:071:59:243:30:336:15:259:00:52WenowconsiderthecomputationoftheirreduciblecomponentsoftheidealIn1,1.
WefollowthestrategydescribedafterTheorem6.
13,usingSage'sdefaultalgorithmtocomputesaturations.
Table3comparesthisstrategy(includingthetimeofAlgorithm1)withthealgorithmfromBinomials[18].
Itcanbeseenthatourmethodismoreecient.
Inparticular,fortheidealI7,1Kahle'salgorithmdidnotnishwithin60hoursofcomputation.
Table3IrreduciblecomponentsoftheidealsIn1,1.
n11234567#components3114013946615284953timeChordalNet0:00:000:00:010:00:040:00:130:02:010:37:3512:22:19Binomials0:00:000:00:000:00:010:00:120:03:004:15:36-ComparingTable2withTable3itisapparentthatcomputingatriangularchordalnetworkrepresentationisconsiderablysimplerthancomputingtheirreduciblecomponents.
Nonethe-less,ifweareonlyinterestedinthehighdimensionalcomponents,thecomplexitycanbesignicantlyimproved.
Indeed,inTable4wecanseehowwecanveryecientlycomputeallcomponentsofthesevenhighestdimensions.
7.
2.
Latticewalks.
Wenowshowasimpleapplicationofourradicalmembershiptest.
Weconsiderthelatticereachabilityproblemfrom[13](seealso[22]).
GivenasetofvectorsBZn,constructagraphwithvertexsetNninwhichu,v∈Nnareadjacentifuv∈±B.
Theproblemistodecidewhethertwovectorss,t∈NnareinthesameconnectedcomponentCHORDALNETWORKSOFPOLYNOMIALIDEALS103Table4HighdimensionalirreduciblecomponentsoftheidealsIn1,1.
Highest5dimensionsHighest7dimensionsn12040608010010203040#comps4046849641244152424425372870212432time0:01:070:04:540:15:120:41:521:34:050:05:020:41:413:03:299:53:09ofthegraph.
ThisproblemisequivalenttoanidealmembershipproblemforacertainbinomialidealIB[13].
Therefore,ourradicalmembershiptestcanbeusedtoprovethats,tarenotinthesameconnectedcomponent(butitmayfailtoprovetheconverse).
Weconsiderthefollowingsampleproblem.
123453252312345*2*2*2*2Figure11.
Illustrationofthecardproblemusing5decks.
Problem7.
1.
Therearencarddecksorganizedonacircle,asshowninFigure11.
Givenanyfourconsecutivedecksweareallowedtomovethecardsasfollows:wemaytakeonecardfromeachoftheinnerdecksandplacethemintheouterdecks(oneineach),orwemaytakeonecardfromtheouterdecksandplacethemintheinnerdecks.
Initiallythenumberofcardsinthedecksis1,2,n.
Isitpossibletoreachastatewherethenumberofcardsinthedecksisreversed3(i.
e.
,theithdeckhasni+1cards)Theaboveproblemisequivalenttodeterminingwhetherfn∈In,wherefn:=x0x21x32···xnn1xn0xn11···xn1,In:={xixi+3xi+1xi+2:0≤iTable5comparesourmethodagainstSingular'sGr¨obnerbasis(grevlexorder)andEpsilon'striangulardecomposition.
EventhoughtheidealInisnotradical,inallexperimentsperformedweobtainedtherightanswer.
Notethatthecomplexityofourmethodisalmostlinear.
ThiscontrastswiththeexponentialgrowthofbothSingularandEpsilon,whichdidnotterminatewithin20hoursforthecasesn=30andn=45.
WedonotincludetimingsforBinomialsandRegularChainssincetheyarebothslowerthanSingularandEpsilon.
7.
3.
Finitestatediagramrepresentation.
Oneoftherstmotivationsinthispaperwastheverynicechordalnetworkrepresentationoftheirreduciblecomponentsoftheidealof3Acombinatorialargumentprovesthatthisisonlypossibleifallprimedivisorsofnareatleast5.
However,thisargumentdoesnotgeneralizetootherchoicesofthenalstate(e.
g.
,wecannotreachastatewherethenumberofcardsis2,1,3,4,5,nforanyn).
104DIEGOCIFUENTESANDPABLOA.
PARRILOTable5Time(seconds)totest(radical)idealmembershipontheidealsIn.
n510152025303540455055ChordalNet0.
73.
08.
514.
321.
829.
837.
748.
262.
370.
684.
8Singular0.
00.
00.
217.
91036.
2Epsilon0.
10.
20.
42.
054.
4160.
15141.
917510.
1---Testresulttruefalsefalsefalsetruefalsetruefalsefalsefalsetrueadjacentminorsofa2*nmatrix.
Wewillseenowthatsimilarchordalnetworkrepresentationsexistforotherdeterminantalideals.
First,noticethatthechordalnetworkinFigure3hasasimplepattern.
Indeed,therearethreetypesofnodesAi={x2ix2i+3x2i+1x2i+2},Bi={0},Ci={x2i,x2i+1},andwehavesomevalidtransitions:Ai→{Ai+1,Bi+1},Bi→{Ci+1},Ci→{Ai+1,Bi+1}.
ThistransitionpatternisrepresentedinthestatediagramshowninFigure12a.
Followingtheconventionfromautomatatheory,wemarktheinitialstateswithanincomingarrowandtheterminalstateswithadoubleline.
x2ix2i+2x2i+1x2i+30x2i,x2i+1(a)2*nmatrixx3ix3i+3x3i+6x3i+1x3i+4x3i+7x3i+2x3i+5x3i+8000x3ix3i+3x3i+2x3i+5,x3i+1x3i+4x3i+2x3i+5x3i,x3i+1,x3i+2(b)3*nmatrixFigure12.
Statediagramsforidealsofadjacentminorsofamatrix.
Wecanalsoconsidertheidealof3*3adjacentminorsofa3*nmatrix.
AsseeninFigure12b,averysimilarpatternarises.
Inordertomakesenseofsuchadiagram,letusthinkofhowtogeneratea3*nmatrixsatisfyingalltheseminorconstraints.
Letv1,vn∈K3denotethecolumnvectors.
Givenvi+1,vi+2,wecangenerateviasfollows:itcanbethezerovector,oritcanbeamultipleofvi+1,oritcanbealinearcombinationofvi+1,vi+2.
Thesethreechoicescorrespondtothethreemainstatesshowninthediagram.
Notenowthatifviisthezerovector,thenwecanignoreitwhenwegeneratevi1andvi2.
Thisiswhyinordertoreachthestate(x3i,x3i+1,x3i+2)wehavetopasstwotrivialstates.
Similarly,ifviisparalleltovi+1,thenwecanignorevi+1whenwegeneratevi1.
Itiseasytoseethattheabovereasoninggeneralizesifweconsidertheadjacentminorsofak*nmatrix.
Therefore,foranyxedk,theidealofadjacentminorsofak*nmatrixhasanitestatediagramrepresentation(andthusithasachordalnetworkrepresentationoflinearsize).
Sincethenodesofthenetworkaregivenbyminors,thenallchainsofthenetworkareoftheformofTheorem6.
13.
Thus,thedecompositionobtainedisintoirreduciblecomponents.
CHORDALNETWORKSOFPOLYNOMIALIDEALS105x2ix2n2x2i+1x2n1x2ix2i+2x2i+1x2i+3x2ix2i+2x2i+1x2i+30x2i,x2i+1x2i,x2i+10x2ix2i+2x2i+1x2i+30x2i,x2i+1Figure13.
Statediagramfortheidealofcyclicallyadjacentminorsofa2*nmatrix.
Manyotherfamiliesofidealsadmitasimplestatediagramrepresentation—forinstance,theidealgeneratedbythencyclicallyadjacentminorsofa2*nmatrix(seeFigure13).
Interestingly,thischordalnetworkhastwoequidimensionalcomponents.
Similarly,theidealof(cyclically)adjacentpermanentalminorshasanitestatediagramrepresentation.
Wecanalsoeasilyprovidefamiliesofzero-dimensionalproblemswithsuchaproperty(e.
g.
,Figure1),sincetheyoftenadmitachordalnetworkoflinearsize(Remark3.
23).
Similarreasoningappliesformonomialideals.
Itisnaturaltoaskforfurtherexamplesofthisbehavior.
Question7.
2.
Characterizeinterestingfamiliesofideals(parametrizedbyn)whosetri-angulardecompositionadmitsanitestatediagramrepresentation(andthushasachordalnetworkrepresentationofsizeO(n)).
Remark7.
3.
Theclassofbinomialedgeideals[16]isanaturalstartingpointforthisquestion,giventhatitgeneralizesboththeidealofadjacentminors(Figure12a)andcyclicallyadjacentminors(Figure13)ofa2*nmatrix.
AppendixA.
Additionalproofs.
A.
1.
Proofsfromsection3.
ProofofLemma3.
10.
LetmAlsoletFm:=F∩K[Xm]betheuniqueinitialnodeofrankm.
Byassumption,Fmiszero-dimensional.
Notethatwhenwecreateanewnodeofrankminaneliminationoperation,wecopytheequationsfromapreviousrankmnode.
Inparticular,wemusthavethatFmFm,andthereforeFmisalsozero-dimensional.
Thisprovesthelemmaforthiscase.
ConsidernowsomepSinceXpisnotmaximal,thereisachildxlofxpsuchthatXl=Xp∪{xl}.
Byinduction,wemayassumethatthelemmaholdsforallnodesofrankl.
ConsiderarankpnodeFpK[Xp]thatwewanttotriangulate,andletFlofranklbeadjacenttoFp.
LetFlbethesameranklnode,butbeforetheltheliminationround.
Byinduction,FlK[Xl]iszero-dimensional.
Therefore,elimp(Fl)K[Xl\{xl}]=K[Xp]isalsozero-dimensional,andaselimp(Fl)Fp,weconcludethatFpiszero-dimensional.
LemmaA.
1.
LetX1,X2X,andletI1K[X1],I2K[X2]beradicalzero-dimensionalideals.
ThenI1+I2K[X1∪X2]isalsoradicalandzero-dimensional.
Proof.
Thisisadirectconsequenceofthefollowingknownfact(see,e.
g.
,[31,Thm.
2.
2]):106DIEGOCIFUENTESANDPABLOA.
PARRILOanidealIK[X]isradicalandzero-dimensionalifandonlyifforanyxi∈Xthereisanonzerosquare-freepolynomialf∈I∩K[xi].
ProofofProposition3.
14.
Foranyl,letXldenotethesubtreeoftheeliminationtreeconsistingofxlandallitsdescendants.
ForachordalnetworkN,wewillsaythatanl-subchainClisthesubsetofachainCrestrictedtonodeswithrankiforsomexi∈Xl.
Notethatanychainisalsoan(n1)-chain.
Thus,itsucestoshowthateveryl-subchainisradicalafterthelthtriangulationroundinAlgorithm1,andweproceedtoshowitbyinduction.
Ifxlisaleafintheeliminationtree,thenanyl-subchainisjusttheoutputofatriangulationoperation,andthusitisradical.
AssumethattheresultholdsforalllLetTpbearankpnodeobtainedafterthepthtriangulationround.
LetCbeap-subchaincontainingTp;wewanttoshowthatCisradical.
Letxl1xlkbethechildrenofxp.
Foreachlj,letCljbethelj-subchainobtainedbyrestrictingCtoranksinXlj.
AlsoletCljbethesamelj-subchain,butbeforetheljtheliminationround.
ObservethatC=Tp+jClj.
NotethatTpiszero-dimensionalandradical,andbyinductionthesameholdsforeachClj.
ItfollowsfromLemmaA.
1thatCisradical.
ProofofProposition3.
20.
Itwasshownin[15]thatthecomplexityofBuchberger'sal-gorithmisqO(k)iftheequationsxqixiarepresent,andthesameanalysisworksforanyq-dominatedideal.
GivenaGr¨obnerbasis,theLexTriangularalgorithm[24]computesatri-angulardecompositionintimeDO(1),whereD≤qkisthenumberofstandardmonomials.
Forirreducible(orsquare-free)decompositions,wecanreducetheproblemtotheunivariatecasebyusingarationalunivariaterepresentation[29](hereweneedthatKcontainssucientlymanyelements).
ThisrepresentationcanalsobeobtainedinDO(1).
Sincethecomplexityofunivariate(square-free)factorization[20]ispolynomialinthedegree(D),theresultfollows.
ProofofLemma3.
22.
Letusseethattheresultholdsaftereachtriangulationandelim-inationround.
WeshowedinLemma3.
15thatafterthelthtriangulationroundallranklnodeshavedisjointvarieties,andthusthereareatmost|V(F∩K[Xl])|≤qκofthem.
Con-sidernowtheltheliminationround,andletusseethatalltheresultingrankpnodes(xpparentofxl)alsohavedisjointvarieties,andthusthesameboundholds.
Assumebyinductionthatallrankpnodeshavedisjointvarietiesbeforetheltheliminationround.
LetFpbearankpnode(beforetheelimination),andletT1,Tkbeitsadjacentranklnodes.
WejustneedtoshowthatthenewrankpnodesFp∪elimp(T1)Fp∪elimp(Tk)havedisjointvarieties(orarethesame).
Byassumption,eachTiK[Xl]denesamaximal(orprime)ideal,andthuselimp(Ti)K[Xl\{xl}]alsodenesamaximalideal.
Therefore,V(elimp(Ti)),V(elimp(Tj))areeitherequalordisjoint,anditfollowsthatthesameholdsforV(Fp∪elimp(Ti)),V(Fp∪elimp(Tj)).
A.
2.
Proofsfromsection4.
LemmaA.
2.
LetLbearing,andletf∈L[y]beamonicunivariatepolynomial.
Letφ:L[y]→L[y]beanendomorphismsuchthatφ(f)=fanddeg(φ(h))≤deg(h)foranyh∈L[y].
Thenφ(hmodf)=φ(h)modfforanyh∈L[y].
CHORDALNETWORKSOFPOLYNOMIALIDEALS107Proof.
ConsidertheEuclideandivisionh=qf+r,whereq,r∈L[y]anddeg(r)Thenφ(h)=φ(q)f+φ(r)anddeg(φ(r))≤deg(r)Itfollowsthatφ(hmodf)=φ(r)=φ(h)modf.
ProofofLemma4.
7.
Weproceedbyinductiononl.
Thebasecase,l=0,isclear.
Assumenowthatthelemmaholdsforsomel,andletusproveitforp:=l+1.
Letfpbearankpnode,andletfl,1,fl,2,fl,kbeitsadjacentranklnodes.
Letusdenotebyφlthefunctionalthatplugsinthevaluesx0,xl.
Byinduction,weknowthatH(fl,i)=φlCl,irCl,ihmodCl,i,wherethesumisoverallfl,i-subchainsCl,i.
NotethatthealgorithmsetsH(fp)=φpirl,iH(fl,i)modfp,whereφpisthefunctionalthatplugsinthevaluexp.
Therefore,H(fp)=φpirl,iφlCl,irCl,ihmodCl,imodfp=φpφliCl,irl,irCl,ihmodCl,imodfp.
Sinceanyfp-subchainisoftheformCp=Cl,i∪{fp}forsomei,wecanrewritetheaboveequationasH(fp)=φpφlCprCphmodCpmodfp,wherethesumisoverallfp-subchainsCp,andwhereCp:=Cp\{fp}.
Tocompletetheproofwejustneedtoseethatφlcommuteswithmodfp.
ThisfollowsfromLemmaA.
2bysettingy=xpandL=K[X\{xp}].
ProofofLemma4.
10.
Letxmidenotethemainvariableofhi,whichisoneoftherankswherethealgorithmisinitialized.
Itisenoughtoprovethelemmaforrankslwherethepaths(intheeliminationtree)startingfromdierentxmirstmeet.
Thus,werestrictourselvestosomem1,mksuchthattheirrespectivepathsallmeetatrankl.
Moreprecisely,weassumethatXlmi∩Xlmj={xl}fori=j,whereXlmidenotesthepathintheeliminationtreeconnectingxmitoxl.
ByapplyingLemma4.
7toeachhi,itfollowsthatthenalvalueofH(fl)isgivenbyplugginginthevaluesofx1,x2,xlinthepolynomialiCirCihimodCi,whereCiisanfl-subchainrestrictedtothepathXlmi.
LetC=iCibethefl-subchainobtainedbycombiningthem.
WewanttoshowthattheaboveexpressionisequaltoCrC(h1hk)modC.
108DIEGOCIFUENTESANDPABLOA.
PARRILONotenowthathidoesnotinvolveanyvariableinXlmjforj=i.
Thus,himodC=himodCi.
ObservethatXlmi,Xlmjhavenocommonarcssincetheyonlymeetatlevell,andthusrC=irCi.
DenotinghCi:=himodCi,theproblemreducestoprovingthefollowingequality:iCirCihCi=CrC1rC2···rCk(hC1+hC2hCk).
(4)Inordertoprove(4),letuslookattheright-handsideasapolynomialinvariableshC1hCk.
NotethatthecoecientofhC1insuchapolynomialisCC1rC1rC2···rCk=rC1ki=2CirCi,andwewanttoshowthatthisexpressionreducestorC1.
RecallthatthescalarcoecientsrCiarenormalized(thiswasthesecondmodicationmadetoAlgorithm3).
ItfollowsthatCirCi=1foralli,andthus(4)holds.
A.
3.
Proofsfromsection6.
ProofofTheorem6.
10.
Wehavetoshowthatchordalityispreserved,thevarietyispre-served,andthechainsintheoutputareregularsystems.
Theproofsofrsttwostatementsareessentiallythesameasforthechordallyzero-dimensionalcase(Lemma3.
11andLemma3.
13).
Itonlyremainstoshowthatthechainsoftheoutputareregularsystems.
Provingthatthechainsaresquare-freeisverysimilar,soweskipit.
LetXldenotethesubtreeoftheeliminationtreeconsistingofxlanditsdescendants.
Wesaythatanl-subchainisthesubsetofachaingivenbynodesofrankiforsomexi∈Xl.
Wewillshowbyinductiononlthatafterthelthtriangulationroundeveryl-subchainisaregularsystem.
Thebasecaseisclear.
AssumethattheresultholdsforalllLetTpbearankpnodeobtainedafterthepthtriangulationround.
LetCbeap-subchaincontainingTp;wewanttoshowthatitisaregularsystem.
ItiseasytoseethatCistriangularandthatcondition(i)fromDenition6.
6issatised.
Wejustneedtocheckcondition(ii).
Letf∈Cbearankkpolynomial;wewanttoshowthatinit(f)(xk+1)=0foranyxk+1∈Z(elimk+1(C)).
Firstconsiderthecasethatk≥p,whichmeansthatf∈Tp.
TheresultfollowsfromthefactthatTpisaregularsystem.
AssumenowthatkThismeansthatfbelongstoanl-subchainCl,whichisasubsetofC.
LetClbethesamel-subchain,butbeforetheltheliminationround.
Byinduction,weknowthatClisaregularsystem,andthusinit(f)(xk+1)=0foranyxk+1∈Z(elimk+1(Cl)).
TheresultfollowsbynoticingthatZ(elimk+1(C))Z(elimk+1(Cl)).
REFERENCES[1]S.
B.
Akers,Binarydecisiondiagrams,IEEETrans.
Computers,100(1978),pp.
509–516.
[2]S.
Arnborg,D.
G.
Corneil,andA.
Proskurowski,Complexityofndingembeddingsinak-tree,SIAMJ.
AlgebraicDiscreteMethods,8(1987),pp.
277–284,https://doi.
org/10.
1137/0608024.
[3]P.
Aubry,D.
Lazard,andM.
M.
Maza,Onthetheoriesoftriangularsets,J.
SymbolicComput.
,28(1999),pp.
105–124.
CHORDALNETWORKSOFPOLYNOMIALIDEALS109[4]J.
R.
BlairandB.
Peyton,Anintroductiontochordalgraphsandcliquetrees,inGraphTheoryandSparseMatrixComputation,Springer,NewYork,1993,pp.
1–29.
[5]H.
L.
BodlaenderandA.
M.
Koster,Combinatorialoptimizationongraphsofboundedtreewidth,Comput.
J.
,51(2008),pp.
255–269.
[6]H.
L.
BodlaenderandA.
M.
Koster,TreewidthcomputationsI.
Upperbounds,Inform.
andComput.
,208(2010),pp.
259–275.
[7]R.
E.
Bryant,Symbolicbooleanmanipulationwithorderedbinary-decisiondiagrams,ACMComputingSurveys(CSUR),24(1992),pp.
293–318.
[8]D.
CifuentesandP.
A.
Parrilo,Anecienttreedecompositionmethodforpermanentsandmixeddiscriminants,LinearAlgebraAppl.
,493(2016),pp.
45–81.
[9]D.
CifuentesandP.
A.
Parrilo,Exploitingchordalstructureinpolynomialideals:AGr¨obnerbasesapproach,SIAMJ.
DiscreteMath.
,30(2016),pp.
1534–1570,https://doi.
org/10.
1137/151002666.
[10]J.
A.
DeLoera,J.
Lee,P.
N.
Malkin,andS.
Margulies,Hilbert'sNullstellensatzandanalgo-rithmforprovingcombinatorialinfeasibility,inProceedingsofthe21stInternationalSymposiumonSymbolicandAlgebraicComputation,ISSAC'08,ACM,NewYork,2008,pp.
197–206.
[11]R.
Dechter,ConstraintProcessing,MorganKaufmann,SanFrancisco,CA,2003.
[12]W.
Decker,G.
Greuel,G.
Pfister,andH.
Sch¨onemann,Singular3-1-6—acomputeralgebrasystemforpolynomialcomputations,http://www.
singular.
uni-kl.
de,2012.
[13]P.
Diaconis,D.
Eisenbud,andB.
Sturmfels,Latticewalksandprimarydecomposition,inMathe-maticalEssaysinHonorofGian-CarloRota,B.
E.
SaganandR.
P.
Stanley,eds.
,Progr.
Math.
161,Birkh¨auserBoston,Boston,MA,1998,pp.
173–193.
[14]S.
N.
Evans,B.
Sturmfels,andC.
Uhler,Commutingbirth-and-deathprocesses,Ann.
Appl.
Probab.
,20(2010),pp.
238–266.
[15]S.
Gao,CountingZerosoverFiniteFieldsUsingGr¨obnerBases,Master'sthesis,CarnegieMellonUni-versity,Pittsburgh,PA,2009.
[16]J.
Herzog,T.
Hibi,F.
Hreinsdottir,T.
Kahle,andJ.
Rauh,Binomialedgeidealsandconditionalindependencestatements,Adv.
Appl.
Math.
,45(2010),pp.
317–333.
[17]E.
Hubert,NotesonTriangularSetsandTriangulation-DecompositionAlgorithmsI:PolynomialSys-tems,Springer,NewYork,2003.
[18]T.
Kahle,Decompositionsofbinomialideals,Ann.
Inst.
Statist.
Math.
,62(2010),pp.
727–745.
[19]M.
Kalkbrener,AgeneralizedEuclideanalgorithmforcomputingtriangularrepresentationsofalgebraicvarieties,J.
SymbolicComput.
,15(1993),pp.
143–167.
[20]E.
Kaltofen,Polynomialfactorization1987–1991,inProceedingsofthe1stLatinAmericanSymposiumonTheoreticalInformatics,I.
Simon,ed.
,Springer,Berlin,Heidelberg,1992,pp.
294–313.
[21]D.
E.
Knuth,CombinatorialAlgorithms,Part1,ArtComput.
Program.
4A,Addison–Wesley,Boston,MA,2011.
[22]S.
R.
Kosaraju,Decidabilityofreachabilityinvectoradditionsystems,inProceedingsofthe14thAnnualACMSymposiumonTheoryofComputing,STOC'82,ACM,NewYork,1982,pp.
267–281.
[23]S.
L.
LauritzenandD.
J.
Spiegelhalter,Localcomputationswithprobabilitiesongraphicalstructuresandtheirapplicationtoexpertsystems,J.
Roy.
Statist.
Soc.
Ser.
B,50(1988),pp.
157–224.
[24]D.
Lazard,Solvingzero-dimensionalalgebraicsystems,J.
SymbolicComput.
,13(1992),pp.
117–131.
[25]F.
Lemaire,M.
M.
Maza,andY.
Xie,TheRegularChainslibrary,inMapleConference(Waterloo,Canada),Vol.
5,2005,pp.
355–368.
[26]M.
M.
Maza,Ontriangulardecompositionsofalgebraicvarieties,presentedattheMEGA-2000Confer-ence,NAG,UK,2000.
[27]M.
MonaganandR.
Pearce,Sparsepolynomialdivisionusingaheap,J.
SymbolicComput.
,46(2011),pp.
807–822.
[28]D.
J.
Rose,R.
E.
Tarjan,andG.
S.
Lueker,Algorithmicaspectsofvertexeliminationongraphs,SIAMJ.
Comput.
,5(1976),pp.
266–283,https://doi.
org/10.
1137/0205021.
[29]F.
Rouillier,Solvingzero-dimensionalsystemsthroughtherationalunivariaterepresentation,Appl.
AlgebraEngrg.
Comm.
Comput.
,9(1999),pp.
433–461.
[30]W.
Steinetal.
,Sage:OpenSourceMathematicalSoftware,http://www.
sagemath.
org,2008.
[31]B.
Sturmfels,SolvingSystemsofPolynomialEquations,CBMSRegionalConf.
Ser.
Math.
97,AMS,Providence,RI,2002.
110DIEGOCIFUENTESANDPABLOA.
PARRILO[32]L.
VandenbergheandM.
S.
Andersen,Chordalgraphsandsemideniteoptimization,Found.
TrendsOptim.
,1(2014),pp.
241–433.
[33]R.
Villarreal,MonomialAlgebras,2nded.
,CRCPress,BocaRaton,FL,2015.
[34]J.
vonzurGathenandJ.
Gerhard,ModernComputerAlgebra,CambridgeUniversityPress,Cam-bridge,UK,2013.
[35]D.
Wang,Computingtriangularsystemsandregularsystems,J.
SymbolicComput.
,30(2000),pp.
221–236.
[36]D.
Wang,EliminationMethods,Springer,NewYork,2001.
[37]D.
Wang,EliminationPractice:SoftwareToolsandApplications,ImperialCollegePress,London,2003.
[38]I.
Wegener,BranchingProgramsandBinaryDecisionDiagrams:TheoryandApplications,DiscreteMath.
Appl.
4,SIAM,Philadelphia,2000.