PARALLEL-PROCESSING ARCHITECTURE FOR THE QUASI-NEWTON METHOD BASED ONBFGS USING ONE-DIMENSIONAL SYSTOLIC ARRAYS

This paper presents a parallel algorithm and its systolic array archit ecture for the BFGS (Broyden, Fletcher, Goldfarb, and Shanno) quasi-Ne wton method of minimizing an n-vector function. The calculation of sea rch direction vectors and the update of approximation to Hessian matri ces by the BFGS updating formula both have O(n(2)) complexity. We firs t 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 calculati on 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). ( C) 1998 Scripta Technica, Electron Comm Jpn Pt 3, 81(10): 73-82, 1998.