English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Rutishauser, Gragg and Harrod and nally H.Y. Zha used the same class of chasing algorithms for transforming arrowhead matrices to tridi- agonal form. Using a graphical theoretical approach, we propose a new chasing algorithm. Although this algorithm has the same sequential computational complexity and backward error properties as the old algorithms, it is better suited for a pipelined approach. The parallel algorithm for this new chasing method is described, with performance results on the Paragon and nCUBE. Comparison results between the old and the new algorithms are also presented. Chasing algorithms are commonly used to nd eigenvalues of tridiagonal ma- trices (4,x8.2). They can also be used to transform matrices to tridiagonal form, such as Rutishauser's algorithm for tridiagonalizing banded matrices (6), Gragg and Harrod's improved version of it, and recently Zha's algorithm for tridiagonalizing arrowhead matrices (10). All of these methods use the standard chasing step of (4, x8.2). We will refer to them as the standard or Zha's algorithm. Using the graph representation of matrices we will show that they correspond to chasing edges of the triangles representing the current entries of the matrix. In this paper, we develop a new algorithm for tridiagonalizing arrowhead matrices based on a new chasing step. Unlike the standard chasing step, the new one uses two additional entries outside the tridiagonal band, and chases nodes instead of edges. The new algorithm can be implemented on parallel architectures using a pipeline approach more eciently than the ones based on the standard chasing step. In the remainder of the paper, a graphical representation of the structure of symmetric matrices is used. The graph of a symmetric n n matrix A consists of nodes 1, 2, ::: ,nwith an edge between nodes i and j if and only if aij6 =0 . The structure of the paper is as follows. Section 2 describes chasing algorithms in general. Section 3 describes the new chasing step. Section 4 describes the algorithm to transform arrowhead matrices to tridiagonal form. Section 5 describes the parallel algorithm and optimal data partitioning for this algorithm.

A new parallel chasing algorithm for transforming arrowhead matrices to tridiagonal form