Processing of linear systems of equations

摘要

A method for processing linear systems of equations and finding a nx1 vector x satisfying Ax=b where A is a symmetric, positive-definite nxn matrix corresponding to nxn predefined high-precision elements and b is an n1 vector corresponding to n predefined high-precision elements. A first iterative process generates n low-precision elements corresponding to an nx1 vector x1 satisfying A1x1=b1 where A1, b1 are elements in low precision. The elements are converted to high-precision data elements to obtain a current solution vector x. A second iterative process generates n low-precision data elements corresponding to an nx1 correction vector dependent on the difference between the vector b and the vector product Ax. Then there is produced from the n low-precision data elements of the correction vector respective high-precision data elements of an nx1 update vector u. The data elements of the current solution vector x are updated such that x=x±u.

主权项

1. A method for generating n high-precision data elements corresponding to an nx1 vector x satisfying Ax=b where A is a symmetric, positive-definite n×n matrix corresponding to nxn predefined high-precision data elements and b is an nx1 vector corresponding to n predefined high-precision data elements, and Ax is a matrix vector product, the method comprising:
(a) implementing, at a hardware processor device, a first iterative process for generating from an input data n low-precision data elements corresponding to an nx1 vector xl satisfying Alxl=bl, where Al is an n×n matrix corresponding to the nxn data elements of matrix A in low precision and bl is an nx1 vector corresponding to the nx1 data elements of vector b in low precision, the method terminating the first iterative process on occurrence of a first convergence condition; (b) converting the data elements of vector x1 to high-precision data elements to obtain a current solution vector x; and generating n data elements corresponding to a current nxl error vector rl in low precision indicative of the difference between the vector b and the matrix vector product Ax; (c) implementing a second iterative process for generating n low-precision data elements corresponding to an nx1 correction vector dependent on the difference between the vector b and the vector product Ax, the hardware processor device implementing control logic for terminating the second iterative process on occurrence of a second convergence condition; wherein a matrix vector product of the matrix Al with said correction vector is equal to the low-precision error vector rl; (d) producing from the n low-precision data elements of said correction vector respective high-precision data elements of an nx1 update vector u; (e) updating the data elements of said current solution vector x such that x=x+u; and (f) performing steps (c) to (e) until occurrence of a third convergence condition, said input data defining the data elements of matrix A comprising a function F defining application of each matrix A element a(i,j) on an element of any nxl vector, where 1≦i≦n and 1≦j≦n are the row and column indices respectively of matrix A elements, the control logic being adapted to use said function F in performance of steps (a) to (e) without having to form said matrix A, wherein processing operations in performing the steps (a) to (e) for solving linear systems of equations involving said matrix A elements a(i,j) are performed in a memory device associated with said hardware processor device, and memory accesses resulting from processing operations of said steps (a) to (c) that generate the matrix vector product with matrix A or Al is substantially reduced.