How to Perform Freivalds algorithm in gnark

[sid-alluri]

I am trying to optimize matrix multiplication with Freivalds' algorithm. It would be helpful to know how to perform Freivalds in gnark.

[ivokub]

See algorithm description https://en.wikipedia.org/wiki/Freivalds%27_algorithm.

On a high level - define Matrix as [N][M]frontend.Variable, then use multicommit to get a random challenge r, compute vector R = [M]frontend.Variable{1, r, r^2, ..., r^M-1} then perform matrix-vector multiplication of input matrices A and B and C.

It would be more helpful if you would post your minimal example with witness generation for debugging. Unfortunately I do not have time to implement full algorithm right now.