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 5.36e-05s (cpu); 0.000210412s (thread); 0s (gc)

              1       1
o6 : Matrix ZZ  <-- ZZ

i7 : ZZ[y];

i8 : time B = sub((y+1)^(2^n),{y=>1})
 -- used 4.7282s (cpu); 3.71764s (thread); 0s (gc)

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.

Citation

If you have used this package in your research, please cite it as follows:

@misc{SLPexpressionsSource,
  title = {{SLPexpressions: straight line programs and algebraic circuits. Version~1.21}},
  author = {Anton Leykin and Timothy Duff and Justin Chen and Mike Stillman},
  howpublished = {A \emph{Macaulay2} package available at
    "http://people.math.gatech.edu/~aleykin3/NAG4M2"}
}

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
- cCode(GateMatrix,GateMatrix,File) (missing documentation)
- cCode(List,List,File) (missing documentation)
- 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
- detGate(GateMatrix) (missing documentation)
- diff(GateMatrix,GateMatrix) -- see differentiating circuits
- diff(InputGate,Gate) -- see differentiating circuits
- diff(InputGate,GateMatrix) -- see differentiating circuits
- evaluate(CompiledSLProgram,MutableMatrix,MutableMatrix) (missing documentation)
- evaluate(InterpretedSLProgram,MutableMatrix,MutableMatrix) (missing documentation)
- 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(Gate,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
- expression(DetGate) (missing documentation)
- expression(DivideGate) (missing documentation)
- expression(GateMatrix) (missing documentation)
- expression(InputGate) (missing documentation)
- expression(ProductGate) (missing documentation)
- expression(SumGate) (missing documentation)
- flatten(GateMatrix) (missing documentation)
- 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
- html(Gate) (missing documentation)
- html(GateMatrix) (missing documentation)
- InputGate .. InputGate -- Passing .. to InputGate names (see code). TO DO: expand this.
- isConstant(InputGate) -- whether an input gate is constant
- makeCompiledSLProgram(GateMatrix,GateMatrix) (missing documentation)
- makeCompiledSLProgram(List,List) (missing documentation)
- 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)
- matrix(GateMatrix) (missing documentation)
- countGates(Gate) -- see measuring the size of circuits
- 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
- net(Gate) (missing documentation)
- toExternalString(InputGate) (missing documentation)
- 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, defined in SLPexpressions.m2, with auxiliary files in SLPexpressions/.

The source of this document is in SLPexpressions/doc.m2:29:0.