bwc failure checking has false negatives.
This issue was recently encountered by @x-RDucha and reported on the mailing list.
More specifically, if lingen finishes with "Number of lucky columns: 0", then it means that its input was corrupted.
To guard against such bad events, a bwccheck
binary exists (see #15127 (closed)).
To use it, the instructions are as follows:
make bwccheck
$build_tree/linalg/bwc/bwccheck prime=2 m=64 n=64 -- $directory_with_bwc_files/[ACV]*
This check is not plugged in the normal course of running bwc.pl, even though it's relatively cheap to run (compared to the rest, that is). It should.
Unfortunately, as it is, the check files that are created by bwc's secure
program to enable the checks that bwccheck
runs are not good enough, and as a result, they let possible false negatives go through anyway. This happened in the context of the report above, and it also happened in the course of a recent record computation.
The reason is that we check a vector w for consistency with its supposed value w=M^K\times v
(for K
=interval) by comparing two dot products, namely (C_K^T=x^T\times M^K)\times v
and (C_0^T=x^T)\times w
, which should be equal. It's a bad idea, since C_0=x
is a sparse vector!
It's much better to compare C_{K+a}^T\times v
and C_a^T\times w
for even a very small value a
, since C_a
is no longer sparse.
To replace the check files $directory_with_bwc_files/C*
with more robust ones:
$build_tree/linalg/bwc/secure [[args as in found in the current invocation as found in bwc.stdout]] check_stops=[[values]]
where the values for check_stops should be as in the notations above. K=interval, and a is something large enough so that C_a
is no longer sparse. Even a constant value should be sufficient. For example, with interval=1024, values such as check_stops=0,16,1024,1040
are good.