Many polynomials can be stored and evaluated efficiently when represented as a straight line program (SLP), also known as an algebraic circuit. By contrast, elements of a PolynomialRing in Macaulay2 are necessarily represented in "expanded" form, e.g. via a monomial basis.
This package provides basic types and methods for constructing and evaluating SLPs.
Here is a simple example illustrating an advantage of SLP representations.
i1 : declareVariable x o1 = x o1 : InputGate |
i2 : f = x + 1 o2 = (x + 1) o2 : SumGate |
i3 : n = 12; |
i4 : for i from 1 to n do f = f*f -- f = (x+1)^(2^n) |
i5 : slp = makeSLProgram({x},{f})
o5 = SLProgram{cache => CacheTable{} }
constant positions => {-2}
constants => | 1 |
number of inputs => 1
number of outputs => 1
RawSLProgram => SLProgram (
consts+vars: 2
noninput nodes: 13
output nodes: 1
)
variable positions => {-1}
o5 : SLProgram
|
i6 : time A = evaluate(slp,matrix{{1}});
-- used 0.000287501 seconds
1 1
o6 : Matrix ZZ <--- ZZ
|
i7 : ZZ[y]; |
i8 : time B = sub((y+1)^(2^n),{y=>1})
-- used 19.0865 seconds
o8 = 104438888141315250669175271071662438257996424904738378038423348328395390
797155745684882681193499755834089010671443926283798757343818579360726323
608785136527794595697654370999834036159013438371831442807001185594622637
631883939771274567233468434458661749680790870580370407128404874011860911
446797778359802900668693897688178778594690563019026094059957945343282346
930302669644305902501597239986771421554169383555988529148631823791443449
673408781187263949647510018904134900841706167509366833385055103297208826
955076998361636941193301521379682583718809183365675122131849284636812555
022599830041234478486259567449219461702380650591324561082573183538008760
862210283427019769820231316901767800667519548507992163641937028537512478
401490715913545998279051339961155179427110683113409058427288427979155484
978295432353451706522326906139490598769300212296339568778287894844061600
741294567491982305057164237715481632138063104590291613692670834285644073
044789997190178146576347322385026725305989979599609079946920177462481771
844986745565925017832907047311943316555080756822184657174637329688491281
952031745700244092661691087414838507841192980452298185733897764810312608
590300130241346718972667321649151113160292078173803343609024380470834040
3154190336
|
i9 : A == B o9 = true |
This documentation describes version 1.14 of SLPexpressions.
The source code from which this documentation is derived is in the file SLPexpressions.m2. The auxiliary files accompanying it are in the directory SLPexpressions/.
The object SLPexpressions is a package.