next | previous | forward | backward | up | top | index | toc | Macaulay2 website
SLPexpressions :: SLPexpressions

SLPexpressions -- Straight Line Programs and expressions for evaluation circuits

Description

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

See also

Authors

Version

This documentation describes version 1.14 of SLPexpressions.

Source code

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/.

Exports

For the programmer

The object SLPexpressions is a package.