Parallel processing architecture for the quasi-Newton method based on BFGS using one-dimensional systolic arrays
✍ Scribed by Kazuyuki Yamauchi; Hiroshi Ohkama; Yoshitaka Fujiwara
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 198 KB
- Volume
- 81
- Category
- Article
- ISSN
- 1042-0967
No coin nor oath required. For personal study only.
✦ Synopsis
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(n 2 ) 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).