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 = makeInterpretedSLProgram({x},{f})

o5 = InterpretedSLProgram{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 : InterpretedSLProgram

i6 : time A = evaluate(slp,matrix{{1}});
     -- used 0.000122056 seconds

              1       1
o6 : Matrix ZZ  <-- ZZ

i7 : ZZ[y];

i8 : time B = sub((y+1)^(2^n),{y=>1})
     -- used 6.42376 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

Authors

Version

This documentation describes version 1.21 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

Types
- CompiledSLProgram (missing documentation)
- DetGate -- see Gate -- the class of all gates
- DivideGate -- see Gate -- the class of all gates
- Gate -- the class of all gates
- InputGate -- see Gate -- the class of all gates
- ProductGate -- see Gate -- the class of all gates
- SumGate -- see Gate -- the class of all gates
- GateMatrix -- a matrix of Gates
- InterpretedSLProgram -- see makeInterpretedSLProgram -- create a straight-line program
- SLProgram (missing documentation)
- ValueHashTable -- see valueHashTable -- creates a hash table of values for evaluation
Functions and commands
- detGate -- see creating gates
- inputGate -- see creating gates
- productGate -- see creating gates
- sumGate -- see creating gates
- declareVariable -- assigns an input gate to a given variable name
- gateMatrix -- create a GateMatrix
- gatePolynomial -- creates an input gate for a given polynomial
- getVarGates -- returns the input gates for variables in a polynomial ring
- makeCompiledSLProgram (missing documentation)
- makeInterpretedSLProgram -- create a straight-line program
- makeSLProgram -- create a straight-line program (either interpreted or compiled)
- setTryJustInTimeCompilation -- see makeSLProgram -- create a straight-line program (either interpreted or compiled)
- countGates -- see measuring the size of circuits
- undeclareVariable -- clears assignment of an input gate to a variable name
- valueHashTable -- creates a hash table of values for evaluation
Methods
- - Gate -- see arithmetic with circuits
- Gate * Gate -- see arithmetic with circuits
- Gate * Matrix -- see arithmetic with circuits
- Gate * Number -- see arithmetic with circuits
- Gate * RingElement -- see arithmetic with circuits
- Gate + Gate -- see arithmetic with circuits
- Gate + Number -- see arithmetic with circuits
- Gate + RingElement -- see arithmetic with circuits
- Gate - Gate -- see arithmetic with circuits
- Gate - Number -- see arithmetic with circuits
- Gate - RingElement -- see arithmetic with circuits
- Gate / Gate -- see arithmetic with circuits
- Gate ^ ZZ -- see arithmetic with circuits
- GateMatrix * GateMatrix -- see arithmetic with circuits
- GateMatrix * Matrix -- see arithmetic with circuits
- GateMatrix * RingElement -- see arithmetic with circuits
- GateMatrix + GateMatrix -- see arithmetic with circuits
- GateMatrix + Matrix -- see arithmetic with circuits
- GateMatrix - GateMatrix -- see arithmetic with circuits
- GateMatrix - Matrix -- see arithmetic with circuits
- GateMatrix ^ List -- see arithmetic with circuits
- Matrix * Gate -- see arithmetic with circuits
- Matrix * GateMatrix -- see arithmetic with circuits
- Matrix + GateMatrix -- see arithmetic with circuits
- Matrix - GateMatrix -- see arithmetic with circuits
- Number * Gate -- see arithmetic with circuits
- Number + Gate -- see arithmetic with circuits
- Number - Gate -- see arithmetic with circuits
- RingElement * Gate -- see arithmetic with circuits
- RingElement * GateMatrix -- see arithmetic with circuits
- RingElement + Gate -- see arithmetic with circuits
- RingElement - Gate -- see arithmetic with circuits
- compress(Gate) -- see compressing circuits
- compress(GateMatrix) -- see compressing circuits
- detGate(List) -- see creating gates
- inputGate(Thing) -- see creating gates
- productGate(List) -- see creating gates
- sumGate(List) -- see creating gates
- vars(IndexedVariable) -- see creating variables as objects of type InputGate
- vars(InputGate) -- see creating variables as objects of type InputGate
- vars(Symbol) -- see creating variables as objects of type InputGate
- declareVariable(IndexedVariable) -- see declareVariable -- assigns an input gate to a given variable name
- declareVariable(InputGate) -- see declareVariable -- assigns an input gate to a given variable name
- declareVariable(Symbol) -- see declareVariable -- assigns an input gate to a given variable name
- declareVariable(Thing) -- see declareVariable -- assigns an input gate to a given variable name
- diff(GateMatrix,GateMatrix) -- see differentiating circuits
- diff(InputGate,Gate) -- see differentiating circuits
- diff(InputGate,GateMatrix) -- see differentiating circuits
- evaluate(SLProgram,Matrix) -- see evaluate(SLProgram,MutableMatrix,MutableMatrix) -- evaluate a straight-line program
- evaluate(SLProgram,MutableMatrix,MutableMatrix) -- evaluate a straight-line program
- value(DetGate,ValueHashTable) -- see evaluating gates
- value(DivideGate,ValueHashTable) -- see evaluating gates
- value(GateMatrix,ValueHashTable) -- see evaluating gates
- value(InputGate,ValueHashTable) -- see evaluating gates
- value(ProductGate,ValueHashTable) -- see evaluating gates
- value(SumGate,ValueHashTable) -- see evaluating gates
- gateMatrix(GateMatrix) -- see gateMatrix -- create a GateMatrix
- gateMatrix(List) -- see gateMatrix -- create a GateMatrix
- gateMatrix(Matrix) -- see gateMatrix -- create a GateMatrix
- gatePolynomial(Matrix) -- see gatePolynomial -- creates an input gate for a given polynomial
- gatePolynomial(RingElement) -- see gatePolynomial -- creates an input gate for a given polynomial
- getVarGates(PolynomialRing) -- see getVarGates -- returns the input gates for variables in a polynomial ring
- InputGate .. InputGate -- Passing .. to InputGate names (see code). TO DO: expand this.
- isConstant(InputGate) -- whether an input gate is constant
- makeInterpretedSLProgram(GateMatrix,GateMatrix) -- see makeInterpretedSLProgram -- create a straight-line program
- makeInterpretedSLProgram(List,List) -- see makeInterpretedSLProgram -- create a straight-line program
- makeSLProgram(GateMatrix,GateMatrix) -- see makeSLProgram -- create a straight-line program (either interpreted or compiled)
- makeSLProgram(List,List) -- see makeSLProgram -- create a straight-line program (either interpreted or compiled)
- setTryJustInTimeCompilation(Boolean) -- see makeSLProgram -- create a straight-line program (either interpreted or compiled)
- countGates(GateMatrix) -- see measuring the size of circuits
- depth(DetGate) -- see measuring the size of circuits
- depth(DivideGate) -- see measuring the size of circuits
- depth(GateMatrix) -- see measuring the size of circuits
- depth(InputGate) -- see measuring the size of circuits
- depth(ProductGate) -- see measuring the size of circuits
- depth(SumGate) -- see measuring the size of circuits
- undeclareVariable(InputGate) -- see undeclareVariable -- clears assignment of an input gate to a variable name
- valueHashTable(List,List) -- see valueHashTable -- creates a hash table of values for evaluation
- determinant(GateMatrix) -- see working with gate matrices
- entries(GateMatrix) -- see working with gate matrices
- GateMatrix _ List -- see working with gate matrices
- GateMatrix _ Sequence -- see working with gate matrices
- GateMatrix | GateMatrix -- see working with gate matrices
- GateMatrix | Matrix -- see working with gate matrices
- GateMatrix || GateMatrix -- see working with gate matrices
- GateMatrix || Matrix -- see working with gate matrices
- Matrix | GateMatrix -- see working with gate matrices
- Matrix || GateMatrix -- see working with gate matrices
- numColumns(GateMatrix) -- see working with gate matrices
- numRows(GateMatrix) -- see working with gate matrices
- submatrix(GateMatrix,List,List) -- see working with gate matrices
- substitute(GateMatrix,GateMatrix,GateMatrix) -- see working with gate matrices
- substitute(GateMatrix,HashTable) -- see working with gate matrices
- substitute(GateMatrix,List) -- see working with gate matrices
- substitute(GateMatrix,Option) -- see working with gate matrices
- transpose(GateMatrix) -- see working with gate matrices

For the programmer

The object SLPexpressions is a package.