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.000304311 seconds 1 1 o6 : Matrix ZZ <--- ZZ |
i7 : ZZ[y]; |
i8 : time B = sub((y+1)^(2^n),{y=>1}) -- used 10.0012 seconds o8 = 1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987 5734381857936072632360878513652779459569765437099983403615901343837183144280700118559462263763188393977127456723346843445866 1749680790870580370407128404874011860911446797778359802900668693897688178778594690563019026094059957945343282346930302669644 3059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032 9720882695507699836163694119330152137968258371880918336567512213184928463681255502259983004123447848625956744921946170238065 0591324561082573183538008760862210283427019769820231316901767800667519548507992163641937028537512478401490715913545998279051 3399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412 9456749198230505716423771548163213806310459029161369267083428564407304478999719017814657634732238502672530598997959960907994 6920177462481771844986745565925017832907047311943316555080756822184657174637329688491281952031745700244092661691087414838507 8411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190336 |
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.