backward error code

[jarlebring]

The code to compute the backward error in the dropbox should be migrated, e.g. compute_theta.jl. Not entirely sure the extent of this since I didn't look closer at the code. There was some generation of data-files involved, which is maybe not so unit test friendly. Some documentation would probably be in order. I'll assign this to max since he implemented this.

[jarlebring]

I have (proabably) temporarily put the simulation code in the directory simulations. Graphs corresponding to table 5.1 in the current manu can be found in simulations/graphs. I hope this is enough structure so we can transfer the backward error code to a useful place.

Data files for the backward error code can maybe be put in simulations/bwerr?

I would be particularly interested in the last column in this table in terms of backward error instead of the printed relative (scalar) error.

Note that monomials on degopt form serves as the best starting graph.

[jarlebring]

After a small typo committed above (can you ok it @mfasi?) I managed to make the bwerr code run. Hopefully I didn't misunderstand anything.

I want to reproduce the theta-values in the SID paper. They have the following table:

The graph corresponding to degree 15+ has four multiplications and is stored in a cgr file:

julia> graph=import_compgraph("simulations/graphs/exp_m4_SID_0_69.cgr");
julia> compute_bwd_theta_exponential(graph,coefftype=Float64,tolerance=eps()/2)[2]
0.6718916439775657
julia> compute_bwd_theta_exponential(graph,coefftype=BigFloat,tolerance=eps()/2)[2]
0.6670747833636483381525295044411905109882354736328125

As far as I can tell, this should be compared with 0.6950 in the table. Maybe this is due to a difference in how the theta is computed. Maybe like this: Since the 15+ polynomial is constructed to match the first 15 terms in the taylor expansion, so they can do the theta computations based on the remainder. In practice the terms do not match exactly (after rounding of the coefficients) and we take these terms into account in our way of computing theta. Do you think this can be the explanation @mfasi?

If so, our way is better. How we present it in the paper is more difficult...

[mfasi]

After a small typo committed above (can you ok it @mfasi?)

Yes, thanks for fixing it.

I managed to make the bwerr code run. Hopefully I didn't misunderstand anything.

I had a look at the code you wrote, and they make sense to me.

julia> graph=import_compgraph("simulations/graphs/exp_m4_SID_0_69.cgr");
julia> compute_bwd_theta_exponential(graph,coefftype=Float64,tolerance=eps()/2)[2]
0.6718916439775657
julia> compute_bwd_theta_exponential(graph,coefftype=BigFloat,tolerance=eps()/2)[2]
0.6670747833636483381525295044411905109882354736328125

As far as I can tell, this should be compared with 0.6950 in the table. Maybe this is due to a difference in how the theta is computed. Maybe like this: Since the 15+ polynomial is constructed to match the first 15 terms in the taylor expansion, so they can do the theta computations based on the remainder. In practice the terms do not match exactly (after rounding of the coefficients) and we take these terms into account in our way of computing theta. Do you think this can be the explanation @mfasi?

Yes, I think that's right. Sastre et al. use a different technique to compute the thetas because they have a series expansion of the residual available. As we don't, I used the customary method for Padé approximants. But I don't think that the difference between the two values is suspicious, roundoff errors certainly play a role, and I believe that the fact that they're both bounds should also be taken into account.

I will close this issue now, as it seems that the all the relevant code in Dropbox has been migrated to GitHub.