System for convergence evaluation for stationary method iterative linear solvers

A system for evaluating the convergence to a solution for a matrix equation including an A-matrix with a plurality of elements whose values are known, an x-vector with a plurality of elements whose values are unknown, and a b-vector with a plurality of elements whose values are known, the system comprising:

• a plurality of field programmable gate arrays (FPGAs), each including a plurality of configurable logic elements and a plurality of configurable storage elements;
• a plurality of update summation units each including—
• a storage element formed from the configurable storage elements and configured to store a portion of a plurality of updates, each update being received from an iterative linear equation solver and representing a difference between a solution value of an element of the x-vector from a current iteration and the solution value of the element of the x-vector from a previous iteration,
• a conversion element formed from the configurable logic elements and configured to determine the absolute value of each of the portion of the plurality of updates, and
• a first summation unit formed from the configurable logic elements and configured to accumulate the absolute value of the portion of the plurality of updates to form a partial sum;
• and
• a global convergence unit including—
• a second summation unit formed from the configurable logic elements and configured to accumulate the partial sums from each update summation unit to form a total sum,
• an epsilon storage element formed from the configurable logic elements and configurable storage elements and configured to generate a convergence factor which varies based on the x-vector input and corresponds to a maximum acceptable total of the differences and is proportional to the number of elements of the x-vector;
• and
• a comparator formed from the configurable logic elements and configured to generate a signal if the total sum is less than the convergence factor.

A method of evaluating the convergence to a solution for a matrix equation including an A-matrix with a plurality of elements whose values are known, an x-vector with a plurality of elements whose values are unknown, and a b-vector with a plurality of elements whose values are known, the method comprising the steps of:

• a) receiving in a field programmable gate array (FPGA) a plurality of updates from an external iterative linear solver, each update representing a difference between a solution value of an element of the x-vector from a current iteration and the solution value of the element of the x-vector from a previous iteration;
• b) determining the absolute value of each of the plurality of updates utilizing a conversion element in the FPGA;
• c) accumulating the absolute value of the plurality of updates utilizing a summation unit in the FPGA;
• d) generating a convergence factor which varies based on the x-vector input and corresponds to a maximum acceptable total of the differences and is proportional to the number of elements of the x-vector;
• e) comparing the accumulated value to the convergence factor utilizing a comparator in the FPGA;
• and
• f) generating a signal if the accumulated value is less than the convergence factor.