A New Way To Solve Linear Equations Over Finite Fields

Recommended Videos

Prasad Raghavendra, an Assistant Professor at University of California, Berkeley, has found a whole new way of looking at and solving linear equations. Current methods of solving linear equations involve approximating the solution and improving upon it iteratively, but Raghavendra’s approach seems to have eliminated the need for guesswork. Here, have some math.

We usually use stuff like the Jacobi Method, where you have to guess the solution before you improve upon it over and over again until you converge upon an answer, or until you’re sufficiently satisfied with its accuracy. Raghavendra’s method instead uses the concept of randomness to narrow down a set of solutions. Initially, it picks a set of random vectors. Then it keeps only those vectors that are solutions to the first equation. It repeats this for the second equation, using randomly chosen linear combinations of the solutions to the first equation, instead of the random vectors. And so on, essentially “pick, remove, combine.”

I suppose picking random vectors is sort of like guessing, but now the number of iterations no longer depends on how accurately you can estimate the solution.

Dick Lipton talked about this in his blog, his analysis far more sophisticated than anything my college-level Linear Algebra can muster. He’s a Professor of Computer Science at Georgia Tech, and had personally talked to Raghavendra on this, so you’re in good hands. Go read his post, and while you’re at it, check out the intensely intelligent discussion in the comments.

Raghavendra has a paper with proof that his method works for finite fields. Here’s the algorithm:

(via Gödel’s Lost Letter and P=NP)

Relevant to your interests


The Mary Sue is supported by our audience. When you purchase through links on our site, we may earn a small affiliate commission. Learn more
related content
Read Article What Caused the Weekend’s Major Aurora Borealis Phenomenon?
Aurora Borealis over a farmhouse.
Read Article Entomologist Brought to Tears in Response to Her Positive Book Reviews
Dr. Megan Wilkerson book: A to Z Bug Facts Coloring Book: Explore 28 Insects With 60+ Unique Facts
Read Article Important Science Alert! NASA Just Sent a Cat Video From Space!
An orange cat chases a laser on a couch with technical graphics superimposed on the image.
Read Article Scientists Make Major Breakthrough in Treating Morning Sickness
A young pregnant woman of African decent sits on a sofa in the comfort of her own home as she cradles her belly with her hands. She is dressed casually as she looks down at her belly with anticipation.
Read Article Guess What? We’re Bringing the Dodo Back!
The dodo from the animated Alice in Wonderland, smoking a pipe.
Related Content
Read Article What Caused the Weekend’s Major Aurora Borealis Phenomenon?
Aurora Borealis over a farmhouse.
Read Article Entomologist Brought to Tears in Response to Her Positive Book Reviews
Dr. Megan Wilkerson book: A to Z Bug Facts Coloring Book: Explore 28 Insects With 60+ Unique Facts
Read Article Important Science Alert! NASA Just Sent a Cat Video From Space!
An orange cat chases a laser on a couch with technical graphics superimposed on the image.
Read Article Scientists Make Major Breakthrough in Treating Morning Sickness
A young pregnant woman of African decent sits on a sofa in the comfort of her own home as she cradles her belly with her hands. She is dressed casually as she looks down at her belly with anticipation.
Read Article Guess What? We’re Bringing the Dodo Back!
The dodo from the animated Alice in Wonderland, smoking a pipe.