Let users of solutions choose between deterministic and probabilitic algorithms (when possible)

[ClementPernet]

As illustrated here https://trac.sagemath.org/ticket/21579#comment:13, the impossible can happen. In this example, once in while, the charpoly over Z is incorrect, because early termination of the Chinese remainder algorithm finished after completing 3 extra modular computations for which the charpoly kept unchanged. Yet the actual charpoly was different (in the det) by a difference divisible by the three last primes.

In the context of chinese remaindering at least (where we have the option), we should let the user the option to choose between

• deterministic
• probabilistic with a parameter epsilon for the max proba of error (hence avoid using this constant number of 3 additional modular computations).

[bdsaunders]

I propose the following convention for all our Las Vegas methods.

1. The user provides a lower bound for the probability of correctness, a float in the range [0..1]. 1 means deterministic is required, 0 means a heuristic is acceptable. In the case of 0 = heuristic, we generally use a method that "never" fails. It just means we don't have a proof for the given situation.

If the function is not set up to achieve the deterministic requirement, it may throw an error when probability 1 is specified. The function may have a default, usually 0 (heuristic) I would think.

It is the obligation of the code to return a result by a method that has been proven to be correct with the specified probability under the assumption of a uniform true random generator (even though it is actually using near-uniform pseudo randomness).

Note that we may give a better (and slower) result when 0 (heuristic) is specified than when a positive probability is given. If the user says probability 1/2 suffices we may act on it and truly have probability of failure at or near 1/2. However our heuristic would do more work, would not consider such a large chance of failure acceptable. I'm thinking of the cases where heuristically we pick a prime, perhaps not quite large enough for the known proof of correctness, but we don't go around picking prime = 2 just because the user has signaled willingness to accept our heuristic, whereas we might pick 2 if it achieves the user's given positive probability lower bound.

2. Upon return, the function may have reset the probability to a larger value. This is an optional feature. It allows to express (2a) that the result has turned out to be deterministically correct, or (2b) the result is correct with higher probability than specified.

For example (2a), if minpoly is to be computed with probability 1/2 and the method deterministically computes a factor of the minpoly, the result is certain when the degree is n, so the code may signal by resetting the probability to 1 in that case. For example (2b), if a function gets its Las Vegas probability with a Freivalds test, the field has size 101, and the user has specified probability 1/2, the code can set the achieved probability to 1 - 1/101.

In LinBox solutions, this can be done without signature change by putting the probability parameter in the method. I presume something similar can be done in ffpack.

On Fri, May 12, 2017 at 8:27 AM, Clément Pernet [email protected] wrote:

As illustrated here [https://trac.sagemath.org/ticket/21579#comment:17], the impossible can happen. In this example, once in while, the charpoly over Z is incorrect, because early termination of the Chinese remainder algorithm finished after completing 3 extra modular computations for which the charpoly kept unchanged. Yet the actual charpoly was different (in the det) by a difference divisible by the three last primes.

In the context of chinese remaindering at least (where we have the option), we should let the user the option to choose between

• deterministic
• probabilistic with a parameter epsilon for the max proba of error (hence avoid using this constant number of 3 additional modular computations).

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/linbox-team/linbox/issues/53, or mute the thread https://github.com/notifications/unsubscribe-auth/ADk6I0q-Z0H_WKY9ea6poEoiuGn46yGcks5r5FBEgaJpZM4NZOMW .

[ClementPernet]

@dsroche : I remember you started working on this topic last year. What's the status of your work? Is there a branch? We are currently willing to fix the structure of Methods and the way we switch to field extensions when needed. Thanks

[bdsaunders]

Rereading my note I see that the first line should have said "Monte Carlo". Las Vegas and Deterministic are indistinguishable to the user...

I think the affected solutions are, over finite field, rank and minpoly (sometimes charpoly?) Over the integers anything subject to early termination and not certified.

Perhaps the probability specified by caller and probability delivered by callee should be two separate parameters to the method.

Dan, I'd be game to help with this (take on certain functions and/or write some documentation for this).

I heard this joke and thought of you: "How do you fix a broken tuba?" Ans: "With a tube o' glue."

On Wed, Mar 13, 2019 at 11:31 AM Clément Pernet [email protected] wrote:

@dsroche https://github.com/dsroche : I remember you started working on this topic last year. What's the status of your work? Is there a branch? We are currently willing to fix the structure of Methods and the way we switch to field extensions when needed. Thanks

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/linbox-team/linbox/issues/53#issuecomment-472473809, or mute the thread https://github.com/notifications/unsubscribe-auth/ADk6I3SGpStZpQix5HJUJDqEs64vr37Oks5vWRnagaJpZM4NZOMW .