Graphs and their manipulation

graph=Compgraph(T::Type=ComplexF64)

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

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.

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.

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.

add_mult!(graph,node,p1,p2)

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

add_ldiv!(graph,node,p1,p2)

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

add_output!(graph,node)

Adds node to the bottom of the list of outputs of the graph.

See also eval_graph, eval_jac, and eval_runerr.

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.

clear_outputs!(graph)

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

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.

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.

del_node!(graph,node)

Deletes node from the graph, and all data associated with it, except for graph.outputs.

See del_output!.

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]

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

v=get_sorted_keys(graph)

Returns a list of all nodes, sorted.

v=get_all_cref(graph)

Returns a list with references to all coefficients in the graph. The list is sorted.

x=get_coeffs(graph, cref=get_all_cref(graph))

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

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.

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

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

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.

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.

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.

graph=import_compgraph(fname)

Reads a graph stored in the computation graph format (cgr) in the file fname.

See also import_compgraph.

p = get_polynomial(graph::Compgraph)

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

p is polynomial of type Polynomial from the package Polynomials.jl.

See also get_polynomial_coefficients.

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.

T=eltpye(graph::Compgraph{T})

Returns the type T of a graph.

bgraph=big(graph::Compgraph{T})

Converts the coefficients of graph to type big(T) and returns bgraph, which is of type Compgraph{big(T)}.

See also Compgraph(T,orggraph::Compgraph).

cgraph=big(graph::Compgraph{T})

Converts the coefficients of graph to type complex(T) and returns cgraph, which is of type Compgraph{complex(T)}.

See also Compgraph(T,orggraph::Compgraph).