Systolic computation of characteristic polynomials of Hessenberg matrices (Q808171)

A scalar multiple \(\sum^{n}_{i=0}P_{n+1,i+1}\lambda^ i\) of the characteristic polynomial of a lower (upper) Hessenberg matrix \(A=(a_{ij})_{i,j=1,...,n}\), with \(a_{ij}=0\) for all \(j=i+2,...,n\) and \(i=1,...,n-2\), can be computed by the very simple recursive algorithm \(P_{i+1}=-\sum^{i}_{j=1}(a_{ij}/a_{i,i+1})P_ j+(1/a_{i,i+1})\tilde P_ i\) \((i=1,...,n-1)\), \(P_{n+1}=\sum^{n}_{j=1}a_{nj}P_ j-\tilde P_ n,\) where \(P_ 1=(1,0,...,0),\) \(P_ i=(P_{ij})_{j=1,...,n+1},\) and \(\tilde P_ i\) denotes a single cyclic right shifted \(P_ i\). The paper provides the implementation of the above algorithm on a so-called instruction systolic array.