Graphs and their manipulation

The computational graph – Compgraph

The computational graph is represented by a struct Compgraph{T}, where T is the type of the coefficients. Each node in the graph is represented by a Symbol, and these node-IDs need to be unique for every node.

GraphMatFun.CompgraphType
graph=Compgraph(T::Type=ComplexF64)

Creates an empty computation graph of with coefficients of type T.

source
graph=Compgraph(T,orggraph::Compgraph)

Converts a graph such that the coefficients become type T. Note that T can be a Number but can be other objects with defined operations, or just Any.

source

Manipulating graph topology

In general a graph is composed of linear combinations $C = \alpha A + \beta B$ (add_lincomb!), multiplication $C = AB$ (add_mult!), and left inverse $C = A^{-1}B$ (add_ldiv!).

GraphMatFun.add_lincomb!Function
add_lincomb!(graph,node,α1,p1,α2,p2)

The operation α1*p1+α2*p2 is added to the graph. The result is stored in node node.

source
add_lincomb!(graph,node,coeffs,nodes)

Adds a linear combination of the nodes (Vector or Tuple) multiplied with coeffs (Vector or Tuple). Returns cref vector.

source
GraphMatFun.add_mult!Function
add_mult!(graph,node,p1,p2)

Adds a multiplication of node p1 and p2 to the graph. The result is stored in node node.

source
GraphMatFun.add_ldiv!Function
add_ldiv!(graph,node,p1,p2)

The operation inv(p1)*p2 is added to the graph. The result is stored in node node.

source

The graph can have multiple outputs and the behavior controlled.

GraphMatFun.del_output!Function
del_output!(graph,node)

Removes the output node from the list of output nodes of the graph. This function does not remove the node from the graph.

source
GraphMatFun.clear_outputs!Function
clear_outputs!(graph)

Clears the list of output nodes of the graph. This function does not remove the node nodes from the graph.

source

It is also possible to merge two graphs, and to rename and delete nodes.

GraphMatFun.merge_graphsFunction
graph=merge_graphs(
graph1,
graph2;
prefix1 = "",
prefix2 = "G2",
skip_basic1 = true,
skip_basic2 = true,
cref1 = Vector(),
cref2 = Vector(),
input1 = :A,
input2 = :A,

)

Takes all the nodes and edges in graph1 and graph2 and generates a new graph. The node names are in graph1 are changed by adding a prefix prefix1 and graph2 correspondingly. The nodes :I and :A are unchanged if skip_basicX=true. All coefficient references crefX are modified accordingly.

source
GraphMatFun.rename_node!Function
rename_node!(graph,src,dest,cref=Vector())

This changes the name of the node src to dest and updates all references to the node, including coefficient references in cref and graph.outputs.

source

Evaluating the graph

GraphMatFun.eval_graphFunction
result=eval_graph(
    graph,
    x;
    vals = nothing,
    input = :A,
    output = size(graph.outputs, 1),
    comporder = nothing,
)

Evaluates a graph in the value x which is typically a scalar value or a matrix. If x is a Vector, the values will be evaluated elementwise.

The comporder is a Vector of nodes specifying in which order the graph should be computed. By default get_topo_order is used.

The output is an Int specifying which node should be considered as output. The output node is graph.outputs[output].

The vals is used to inspect contents other than the output inside the graph. Typically vals is a Dict. It will be modified to contain the computed nodes of the graph. If we wish to inspect node X3, we can initiate an empty dict as input:

julia > vals = Dict{Symbol,Any}();
julia > eval_graph(graph, A, vals = vals);
julia > vals[:X3]
source
GraphMatFun.get_topo_orderFunction
(order,can_be_deallocated,max_nodes)=get_topo_order(
    graph;
    priohelp = Dict{Symbol,Float64}(),
    free_mem_bonus = 1000,
    will_not_dealloc = [:I],
    input = :A,
)

Computes a topological sort of graph, that is, an ordering of the nodes following which the function the graph represents can be evaluated. The priohelp kwarg can be used to obtain a different topological ordering by changing the node priority. The code assumes that the nodes :I and input do not need to be computed.

The code uses a heuristic to minimize pathwidth. It is based on a point system. You can influence the computation order by providing a priohelp. If you want node :B4 to be computed earlier, you can set priohelp[:B4]=-5000.0. The free_mem_bonus is used in the heuristic to prioritize the computation of nodes which release other nodes. The vector will_not_deallocate influences the order specifying nodes that will not be deallocated and therefore gets no free_mem_bonus.

The return value order is a Vector of Symbols, and can_be_deallocated is a Vector{Vector{Symbol}} where the element i specifies the Symbols that are unused after step i in the ordering. The max_nodes is the pathwidth.

source

Nodes and coefficients

GraphMatFun.get_coeffsFunction
x=get_coeffs(graph, cref=get_all_cref(graph))

Gets the coefficient values for the coefficients specified in cref::Vector.

source
GraphMatFun.set_coeffs!Function
set_coeffs!(graph, x, cref=get_all_cref(graph))

Sets the coefficient values in the coefficients specified in cref::Vector to the values in the vector in x::Vector.

source

Errors and error bounds

GraphMatFun.compute_bwd_thetaFunction
(e_bwd,theta)=compute_bwd_theta(;
    bnd_rel_err = compute_bnd_rel_bwd_err(:exp, graph),
    tolerance = eps(coefftype) / 2,
    theta_init = big"0.2",
    use_log = false,
)

(e_bwd,theta)=compute_bwd_theta(
    graph::Compgraph{T};
    coefftype = T,
    numterms = 100,
    numdigits = 100,
    tolerance = eps(coefftype) / 2,
    theta_init = big"0.2",
    use_log = false,
)

Compute bound on relative backward error with corresponding theta.

The first output $e_{bwd}$ is a function that returns a bound on the relative backward error of the polynomial underlying the computational graph graph, seen as an approximant to the exponential. For the underlying polynomial $p$, the function returns a bound on |δ| where δ is such that exp(z+δ) = p(z). This function is computed using compute_bnd_rel_bwd_err(:graph).

The second output $θ$ is the largest positive real number such that $e_{bwd}(θ) ≤ tolerance$, where $tolerance$ is by default the unit roundoff of the data type coefftype, which in turn defaults to the type of the coefficients of graph.

The value of $theta$ is estimated by approximately solving the equation $e_{bwd}(z) = tolerance$, using the built-in function fzero with starting value set to theta_init. By default this root-finding procedure uses high-precision arithmetic.

If the kwarg use_log is set to true, then the value of $theta$ is computed by approximating a solution to the equation $log(e_{bwd}(z)) = log(tolerance)$ instead.

The alternative form accepts a function that returns a bound on the relative backward error. By default, the function is constructed with compute_bnd_rel_bwd_err(:exp, ...) and the default values for the kwargs in the first form.

source
GraphMatFun.compute_fwd_thetaFunction
(e_fwd,theta)=compute_fwd_theta(
    graph::Compgraph{T},
    f;
    coefftype = T,
    tolerance = eps(coefftype) / 2,
    theta_init = big"0.1",
)

Return relative forward error and corresponding theta for approximation to f.

The first output $e_{fwd}$ is the function that computes the relative forward error$e_{fwd}(z)=|f(z) - p(z)| / |z|$, where $p$ is the polynomial underlying the computational graph graph. This is meaningful only if $p$ approximates $f$ in some sense.

The second output $θ$ is the largest positive real number such that $e_{fwd}(θ) ≤ tolerance$, where $tolerance$ is by default the unit roundoff of the data type coefftype, which in turn defaults to the type of the coefficients of graph.

The value of $θ$ is approximated by using the built-in function fzero with starting value set to theta_init. By default, this root-finding procedure uses high-precision arithmetic.

source
GraphMatFun.compute_bnd_rel_bwd_errFunction
e_bwd=compute_bnd_rel_bwd_err(
    f,
    graph::Compgraph{T};
    coefftype = T,
    numterms = 100,
    numdigits = 100,
)

Compute a bound on the relative backward error of the function f.

The returned function $e_{bwd}$ is a bound on the relative backward error of the polynomial underlying the computational graph graph, seen as an approximant to f. For the underlying polynomial $p$, the function returns a bound on |δ| where δ is such that $f(z+δ) = p(z)$.

The first argument f is a symbol. Currently supported values include:

  • :exp The bound is computed by means of the identity δ = log((exp(-z) p(z)-1)+1). The code computes the series expansion of the right-hand side of the equation, truncates it to the first numterms coefficients, bounds each coefficient of the ensuing polynomial with its absolute value. The computation uses numdigits digits of precision.
source
GraphMatFun.eval_runerrFunction
err=eval_runerr(
    graph,
    x;
    vals = nothing,
    relerrs = nothing,
    input = :A,
    output = size(graph.outputs, 1),
    mode = :bounds, # Can be :bounds, :rand, :estimate
    add_relerr = eps(),
)

Provides the running error of the graph evaluated in x. See eval_graph for meaning of vals and output. The kwarg relerrs is an anologous variable for the running error estimates in each node. The kwarg mode can be :bounds, :rand, :estimate, specifying if the code should make estimates or bounds, or random error within the bound.

source

Reading and writing graphs to file

GraphMatFun.export_compgraphFunction
function export_compgraph(
        graph,
    fname;
    order = get_topo_order(graph)[1],
    fun = "",
    dom = "",
    err = "",
    genby = "",
    descr = "",
    user = splitdir(homedir())[end],
)

Exports the graph to the file fname using the computation graph format (cgr). These kwargs are strings or values that are stored as comments in the file

  • descr of the graph
  • fun function it approximates
  • dom domain it approximates
  • err error in this domain
  • genby script that generated this file
  • user a username that created the file

These kwarg influence how the graph is stored:

  • order specifies an order the graph nodes are stored

CGR format:

Every line corresponds to a node / operation. The syntax is matlab compatible, although gen_code produces faster matlab code.

See also export_compgraph.

source

Helpers and convenience functions

GraphMatFun.get_polynomial_coefficientsFunction
c = get_polynomial_coefficients(graph::Compgraph)

Return the coefficients of the polynomial underlying the computational graph. The graph is assumed to involve only linear combinations and multiplications.

The coefficients c is a vector containing the coefficients as expressed in the monomial basis and sorted from the leading coefficient to the constant term.

See also get_polynomial.

source
Base.eltypeFunction
T=eltpye(graph::Compgraph{T})

Returns the type T of a graph.

source