Numerical experiments with the symmetric algorithm in the ABS class for linear systems.

*(English)*Zbl 0616.65032This paper, which presents numerical comparisons of many symmetric implementations of Abaffy-Broyden-Spedicato (ABS) type algorithms, is a sequel to the earlier paper by the current authors and C. Broyden [(1) Numer. Math. 45, 361-376 (1984; Zbl 0535.65009)] which describes such methods for the solution of the linear system
\[
A^ Tx=b,\quad x\in {\mathbb{R}}^ n,\quad b\in {\mathbb{R}}^ m.
\]
The ABS class of methods may be considered as a generalization of Brown and Brent type methods for non-linear systems as restricted to linear systems. In this paper symmetric rank one updates are used for the ’reflection’ matrix \(H_ i\) and the basic step, given an initial \(x_ 1\), \(H_ 1\) and current approximate solution \(x_ i\) is:

Compute search direction: \(p_ i=H_ i^ Tz_ i\)

Update approximation: \(x_{i+1}=x_ i-(v_ i^ T(A^ Tx_ i-b)/p_ i^ TAv_ i)p_ i\)

Update \(H_ i:\) \(H_{i+1}=H_ i-H_ iAv_ iw_ i^ TH_ i,\)

v\({}_ i\), \(w_ i\) and \(z_ i\) are chosen subject to some restrictions and particular variants use different choices of these parameters. Here 54 variants use six \(w_ i\) and nine \(z_ i\), which are identical in the absence of rounding error. Comparisons are also made with modified Gram-Schmidt, conjugate gradient and QR-methods. Test problems used were all relatively small and dense, with moderate ill-conditioning, having all-integer elements, using a preassigned integer entries solution in an attempt to extend the more limited test problems used in (1).

Results indicate that the choice of \(z_ i\) was much more critical than that of \(w_ i\), with 5 choices of \(z_ i\) giving similar good results, better than for the other methods above. The extensive tables of results present both relative solution error and relative residual error.

The authors state that they hope to perform similar comparisons on large scale problems with non-integer coefficients ’with the aim of producing high quality software based on the symmetric algorithm’.

Compute search direction: \(p_ i=H_ i^ Tz_ i\)

Update approximation: \(x_{i+1}=x_ i-(v_ i^ T(A^ Tx_ i-b)/p_ i^ TAv_ i)p_ i\)

Update \(H_ i:\) \(H_{i+1}=H_ i-H_ iAv_ iw_ i^ TH_ i,\)

v\({}_ i\), \(w_ i\) and \(z_ i\) are chosen subject to some restrictions and particular variants use different choices of these parameters. Here 54 variants use six \(w_ i\) and nine \(z_ i\), which are identical in the absence of rounding error. Comparisons are also made with modified Gram-Schmidt, conjugate gradient and QR-methods. Test problems used were all relatively small and dense, with moderate ill-conditioning, having all-integer elements, using a preassigned integer entries solution in an attempt to extend the more limited test problems used in (1).

Results indicate that the choice of \(z_ i\) was much more critical than that of \(w_ i\), with 5 choices of \(z_ i\) giving similar good results, better than for the other methods above. The extensive tables of results present both relative solution error and relative residual error.

The authors state that they hope to perform similar comparisons on large scale problems with non-integer coefficients ’with the aim of producing high quality software based on the symmetric algorithm’.

Reviewer: A.Swift

##### MSC:

65F05 | Direct numerical methods for linear systems and matrix inversion |

65F10 | Iterative numerical methods for linear systems |

##### Keywords:

testing of numerical methods; orthogonal factorization methods; Gram- Schmidt method; conjugate gradient method; numerical comparisons; symmetric implementations of Abaffy-Broyden-Spedicato (ABS) type algorithms; Brown and Brent type methods; symmetric rank one updates; QR- methods; ill-conditioning
PDF
BibTeX
XML
Cite

\textit{J. Abaffy} and \textit{E. Spedicato}, Optimization 18, 197--212 (1987; Zbl 0616.65032)

Full Text:
DOI

##### References:

[1] | Abaffy J., Dipartimento di Matematica (1985) |

[2] | DOI: 10.1007/BF01391414 · Zbl 0535.65009 · doi:10.1007/BF01391414 |

[3] | Huang H.Y., Journal of Optimization Theory and Applications 16 pp 5– (1975) |

[4] | Stoer J., Introduction to Numerical Analysis (1980) · Zbl 0423.65002 |

[5] | Abaffy J., Dipartimento di Matematica 83 (1983) |

[6] | Abaffy J., Dipartimento di Matematica 83 (1983) |

[7] | Rutishauser H., Editions de la Faculte de Sciences de Besancon (1968) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.