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

DOI10.1515/mcma-2020-2076zbMath1470.65087arXiv1705.10449OpenAlexW3094546928MaRDI QIDQ2026637

Hao Ji, Yaohang Li, Michael Mascagni

Publication date: 20 May 2021

Published in: Monte Carlo Methods and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.10449

zbMATH Keywords

fault-tolerancefailure probabilitymatrix multiplicationGaussian random vectoralgorithmic resilienceGaussian variant of Freivalds' algorithm

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Applications of statistics (62P99) Numerical linear algebra (65F99)

Related Items (1)

Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs

Uses Software

• BLAS
• Algorithm 679

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Bounds on sample space size for matrix product verification
• Deterministic Verification of Integer Matrix Multiplication in Quadratic Time
• Efficiently Correcting Matrix Products
• Importance Sampling for a Monte Carlo Matrix Multiplication Algorithm, with Application to Information Retrieval
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Algorithm-Based Fault Tolerance for Matrix Operations
• The Use of BLAS3 in Linear Algebra on a Parallel Processor with a Hierarchical Memory
• Algorithm 679: A set of level 3 basic linear algebra subprograms: model implementation and test programs
• Stability of block algorithms with fast level-3 BLAS
• A fast normal random number generator
• Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation
• Exact and Approximated Error of the FMA
• Multiplying matrices faster than coppersmith-winograd
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
• A Property of the Normal Distribution

This page was built for publication: Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification