[petsc-dev] TAO method selection (was "coding style")

[Jed Brown]

"Oxberry, Geoffrey Malcolm" <oxberry1 at llnl.gov> writes:
> I can’t think of one either. What is the origin of the algorithm PETSc
> uses for MatMultEqual, and why use this algorithm instead of
> Freivalds' algorithm? I realize you can probably use similar
> probabilistic arguments for the PETSc algorithm as those used for
> Freivalds’ — the current PETSc docs don’t give any intuition for how
> to choose the number of random vectors, and knowing that the
> probability of a false positive is bounded above by 1/2^{n}, where n
> is the number of random vectors chosen, helps guide a sensible
> selection. (n = 5 corresponds to at most ~3% one-sided error)

I think the only difference is that PETSc uses a uniform distribution
over [0,1] while Freivalds uses a boolean {0,1}.  In the convergence
proof for Freivalds' method, I believe this is the difference between

  (1/2)^k == (probability of guessing a boolean)^k

and

  (probability of guessing a real number)^k

which is much smaller (depends on epsilon).  I think Freivalds'
algorithm was chosen only because the proof was convenient and
independent of floating point representation (and enables glossing over
the very real problem that floating point comparisons must involve
tolerances, which would be a conspicuous omission if he had used
continuous random variables).
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 818 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20160819/2ae8d848/attachment.sig>