Parallel processing architecture for the quasi-Newton method based on BFGS using one-dimensional systolic arrays
Kazuyuki Yamauchi, Hiroshi Ohkama, Yoshitaka Fujiwara · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1998
This paper presents a parallel algorithm and its systolic array architecture for the BFGS (Broyden, Fletcher, Goldfarb, and Shanno) quasi-Newton method of minimizing an n-vector function. The calculation of search direction vectors and the update of approximation to Hessian matrices by the BFGS updating formula both have O(n2) complexity. We first introduce an algorithm suitable for parallel processing by employing UD factorization of the approximation to the Hessian. Then, systolic arrays with some FIFO and LIFO memories are proposed for the calculation of search direction vectors and the processing of the BFGS updating formula. The hardware complexity of the proposed parallel processing architecture is O(n), and the parallel time complexity is also O(n). © 1998 Scripta Technica, Electron Comm Jpn Pt 3, 81(10): 73–82, 1998