Rūsiņš Mārtiņš Freivalds — Latvian computer scientist and mathematician

Freivalds' algorithm

Freivalds' algorithm is a randomized method to verify whether the product of two n-by-n matrices A and B equals a third matrix C without performing full multiplication. The algorithm picks a random vector r and checks whether A(B r) equals C r. Each iteration runs in roughly O(n^2) time and has a bounded error probability; repeating the test reduces the chance of a false positive exponentially. This approach is a simple and influential example of how randomness can be used to speed up verification tasks and it is commonly taught in courses on algorithms and complexity theory.

Career, teaching and influence

After completing his studies at Moscow State University, Freivalds returned to Latvia and spent much of his career at the University of Latvia. He supervised several students who went on to international recognition, including Daina Taimina (known for work connecting geometry and mathematical exposition) and Andris Ambainis (known for contributions to quantum computing and complexity). His work bridged mathematics and early theoretical computer science in Latvia during the late Soviet and post-Soviet periods.

Legacy and notable facts

• Member of the Latvian Academy of Sciences from 1992.
• Creator of a widely cited randomized verification algorithm that remains a textbook example.
• Mentor to students who contributed to geometry, algorithms, and quantum computation.

Freivalds died of a heart attack on 4 January 2016 in Riga, aged 73. He was born in Cesvaine, and his career left a lasting mark on algorithmic thinking in Latvia and beyond.