English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this article, we consider the general problem of checking the correctness of matrix multiplication. Given threen  ×  nn\times n    matrices ,  and , the goal is to verify thatA  ×  B   =  CA\times B=C    without carrying out the computationally costly operations of matrix multiplication and comparing the productA  ×  BA\times B    with , term by term. This is especially important when some or all of these matrices are very large, and when the computing environment is prone to soft errors. Here we extend Freivalds’ algorithm to a Gaussian Variant of Freivalds’ Algorithm (GVFA) by projecting the productA  ×  BA\times B    as well as  onto a Gaussian random vector and then comparing the resulting vectors. The computational complexity of GVFA is consistent with that of Freivalds’ algorithm, which isO  ⁢   (   n  2   )O(n^{2})   . However, unlike Freivalds’ algorithm, whose probability of a false positive is2   -  k2^{-k}   , where  is the number of iterations, our theoretical analysis shows that, whenA  ×  B   ≠  CA\times B\neq C   , GVFA produces a false positive on set of inputs of measure zero with exact arithmetic. When we introduce round-off error and floating-point arithmetic into our analysis, we can show that the larger this error, the higher the probability that GVFA avoids false positives. Moreover, by iterating GVFA  times, the probability of a false positive decreases asp  kp^{k}   , where  is a very small value depending on the nature of the fault on the result matrix and the arithmetic system’s floating-point precision. Unlike deterministic algorithms, there do not exist any fault patterns that are completely undetectable with GVFA. Thus GVFA can be used to provide efficient fault tolerance in numerical linear algebra, and it can be efficiently implemented on modern computing architectures. In particular, GVFA can be very efficiently implemented on architectures with hardware support for fused multiply-add operations.

Gaussian variant of Freivalds’ algorithm for efficient and reliable matrix product verification