Computing a matrix symmetrizer exactly using modified multiple modulus residue arithmetic (Q1097642)

A multiple-modulus residue arithmetic is introduced and applied to computing an error-free matrix symmetrizer (i.e., a symmetric nonsingular X satisfying \(XA=A\) tX). In particular, when \(A=(a_{ij})\) is a lower Hessenberg matrix, with nonzero codiagonal elements, then the method recovers the following simple and elegant recursive algorithm to compute a symmetrizer, suggested by Datta (unpublished): Let x 1,x 2,...,x n be the rows of a symmetrizer X to be computed. Step 1: Choose \(x\quad n=(\alpha,0,...,0),\) where \(\alpha\neq 0\) is arbitrary; Step 2 Compute \(x^{n-1},x^{n-2},...,x\) 1 recursively from \(x\quad i=(1/a_{i,i+1})\times (x^{i+1}A-a_{i+1,i+1}x^{i+1}-a_{i+2,\quad i+1}x^{i+2}-...-a_{n,i+1}x\quad n),\) \(i=n-1,...,1\); Step 3: Print x 1,x 2,...,x n and stop.