Two-Level Block Decompositions for Solving Helmholtz Equation via Chebyshev Pseudo Spectral Method

In this paper, we consider solving the Helmholtz equation in the Cartesian domain , subject to homogeneous Dirichlet boundary condition, discretized with the Chebyshev pseudo-spectral method. The main purpose of this paper is to present the formulation of a two-level decomposition scheme for decoupling the linear system obtained from the discretization into independent subsystems. This scheme takes advantage of the homogeneity property of the physical problem along one direction to reduce a 2D problem to several 1D problems via a block diagonalization approach and the reflexivity property along the second direction to decompose each of the 1D problems to two independent subproblems using a reflexive decomposition, effectively doubling the number of subproblems. Based on the special structure of the coefficient matrix of the linear system derived from the discretization and a reflexivity property of the second-order Chebyshev differentiation matrix, we show that the decomposed submatrices exhibits a similar property, enabling the system to be decomposed using reflexive decompositions. Explicit forms of the decomposed submatrices are derived. The decomposition not only yields more efficient algorithm but introduces coarse-grain parallelism. Furthermore, it preserves all eigenvalues of the original matrix.

Block Decompositions and Applications of Generalized Reflexive Matrices

Generalize reflexive matrices are a special class of matrices ?that have the relation where? and ?are some generalized reflection matrices. The nontrivial cases ( or ) of this class of matrices occur very often in many scientific and engineering applications. They are also a generalization of centrosymmetric matrices and reflexive matrices. The main purpose of this paper is to present block decomposition schemes for generalized reflexive matrices of various types and to obtain their decomposed explicit block-diagonal structures. The decompositions make use of unitary equivalence transformations and, therefore, preserve the singular values of the matrices. They lead to more efficient sequential computations and at the same time induce large-grain parallelism as a by-product, making themselves computationally attractive for large-scale applications. A numerical example is employed to show the usefulness of the developed explicit decompositions for decoupling linear least-square problems whose coefficient matrices are of this class into smaller and independent subproblems.

Decompositions of Some Special Block Tridiagonal Matrices

In this paper, we present a unified approach to decomposing a special class of block tridiagonal matrices K (α ,β ) into block diagonal matrices using similarity transformations. The matrices K (α ,β )∈ Rpq× pq are of the form K (α ,β = block-tridiag[β B,A,α B] for three special pairs of (α ,β ): K (1,1), K (1,2) and K (2,2) , where the matrices A and B, A, B∈ Rp× q , are general square matrices. The decomposed block diagonal matrices (α ,β ) for the three cases are all of the form: (α ,β ) = D1 (α ,β ) ⊕ D2 (α ,β ) ⊕---⊕ Dq (α ,β ) , where Dk (α ,β ) = A+ 2cos ( θk (α ,β )) B, in which θk (α ,β ) , k = 1,2, --- q , depend on the values of α and β. Our decomposition method is closely related to the classical fast Poisson solver using Fourier analysis. Unlike the fast Poisson solver, our approach decomposes K (α ,β ) into q diagonal blocks, instead of p blocks. Furthermore, our proposed approach does not require matrices A and B to be symmetric and commute, and employs only the eigenvectors of the tridiagonal matrix T (α ,β ) = tridiag[β b, a,αb] in a block form, where a and b are scalars. The transformation matrices, their inverses, and the explicit form of the decomposed block diagonal matrices are derived in this paper. Numerical examples and experiments are also presented to demonstrate the validity and usefulness of the approach. Due to the decoupled nature of the decomposed matrices, this approach lends itself to parallel and distributed computations for solving both linear systems and eigenvalue problems using multiprocessors.