Narrow Results

In this work we apply a methodology for the parallelization of algorithms for tridiagonal solvers. We classify tridiagonal solvers as a function of their data flows and present a unified version of the projection of these algorithms onto computers with mesh topology and distributed memory. Finally, we evaluate the algorithms and compare them through specific tests on the Fujitsu AP1000.

A partitioning algorithm for solving tridiagonal system of linear equations which is suitable for implementation on multiprocessor systems with small to moderate number of processors is described in this paper. The method is based on decomposing a matrix of order n×n into p partitions of size n×k, where n=pk. The fundamental idea of the proposed algorithm is that the elimination is performed using alternatively superdiagonal and subdiagonal elements, contrary to the Gaussian elimination which uses main diagonal elements. Performance results obtained when the proposed algorithm is implemented on the p-processor orthogonal and linear arrays, both of MIMD type, are presented.

Let 𝔽 denote a field and let V denote a vector space over 𝔽 with finite positive dimension. We consider a pair of linear transformations A : V → V and A* : V → V that satisfy the following conditions: (i) each of A, A* is diagonalizable; (ii) there exists an ordering of the eigenspaces of A such that A* V_i ⊆ V_i-1 + V_i + V_i+1 for 0 ≤ i ≤ d, where V_-1 = 0 and V_d+1 = 0; (iii) there exists an ordering of the eigenspaces of A* such that for 0 ≤ i ≤ δ, where and ; (iv) there is no subspace W of V such that AW ⊆ W, A* W ⊆ W, W ≠ 0, W ≠ V. We call such a pair a tridiagonal pair on V. It is known that d = δ, and for 0 ≤ i ≤ d the dimensions of V_i, , V_d-i, coincide. Denote this common dimension by ρ_i and call A, A*sharp whenever ρ₀ = 1. Let T denote the 𝔽-subalgebra of End_𝔽(V) generated by A, A*. We show: (i) the center Z(T) is a field whose dimension over 𝔽 is ρ₀; (ii) the field Z(T) is isomorphic to each of E₀TE₀, E_dTE_d, , , where E_i (resp. ) is the primitive idempotent of A (resp. A*) associated with V_i (resp. ); (iii) with respect to the Z(T)-vector space V the pair A, A* is a sharp tridiagonal pair.