Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. on Scientific Computing, 18:1446--1461, 1997.  @ NUS  Home/Search   Document Details and Download   Summary   Related Articles   Check

.... for solving the ARE (5) As our focus is on high performance computing and particularly on parallel algorithms for distributed memory architectures, our methods for solving Lyapunov equations will be based on the sign function method which is known to be easily and eciently parallelizable; see [4, 5, 10, 20]. A sign function based Lyapunov solver is then also used in the inner loop of Newton s method for solving AREs; we use the same procedure to solve (5) 3.1 Solving stable Lyapunov equations with the sign function method In this section we describe Lyapunov equation solvers based on the matrix ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. Sci. Comput., 18:1446-1461, 1997.

....is not scalable [15] and the parallelization results [15] are far from those of usual matrix factorizations [9] Therefore we employ a technique based on the matrix sign function. It is well known that sign function based computations are easy to parallelize and yield very ecient code; see, e.g. [1]. The solution of Lyapunov equations using the sign function method was rst described in [19] Ecient algorithms for solving a pair of Lyapunov equations as in (4) are reported in [2, 16] The counterpart of the sign function method for solving Stein equations as in (5) is the squared Smith ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. Sci. Comput., 18:1446-1461, 1997.

....12 BENNER, BYERS, MAYO, QUINTANA AND HERN ANDEZ Table 2 Performance of the communication libraries. Library ( s. 1 (Mbps. Short messages Long messages MPI GM API 37.4 213.1 254.4 for the execution time of the routines are oversimplistic and neglect many of these factors; see, e.g. [3, 17]. We therefore do not pursue this goal any further. 5. EXPERIMENTAL RESULTS Our experiments are performed on a cluster of Intel Pentium II processors at 300 MHz, with 128 MB of RAM each, using IEEE double precision floating point arithmetic ( 2:2 10 16 ) An implementation of BLAS ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. Sci. Comput., 18:1446--1461, 1997.

....made from the earlier sections were merely due to the fact that we restricted ourselves in this paper to discussing the parallel implementation of widely used QR algorithms. In contrast, we mention the advantages of using the QR algorithm: ffl Fewer flops; Fast Convergence. In many cases, cf. [5]) other algorithms can require several times the number of floating point calculations (although they can be in matrix multiplication. ffl High Accuracy. The QR algorithm has always remained one of the most accurate algorithms for the unsymmetric Schur decomposition. ffl Parallelism. This ....

Bai, Z., Demmel, J., Dongarra, J., Petitet, A., Robinson, H., Stanley, K., The Spectral Decomposition of Nonsymmetric Matrices on Distributed Memory Parallel Computers, LAPACK working note 91, University of Tennessee, Jan. 1995

....be determined by the staircase algorithm of Van Dooren [24] See also the code GUPTRI of Demmel and Kagstrom [20] QR LIKE ALGORITHMS 13 7. Divide and Conquer Algorithms To round out the paper we consider a completely different class of algorithm that has been under development in recent years [5, 4]. They are not usually viewed as GZ algorithms, but that is what they are. They are explicit GZ algorithms; that is, they actual compute f(AB Gamma1 ) and f(B Gamma1 A) and their GR decompositions explicitly. They require more computation than a conventional implicit GZ algorithm does, but ....

Z. Bai et. al., The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers, Tech. Rep. CS-95-273, University of Tennessee, 1995.

....iterations. Specifically, the Newton iteration is applied until kH k 1 Gamma H k k 1 and, from then on, the Newton Schulz iteration is used. This switching criterion shows a good behavior in practice. Other less effective criteria have also been tested. For instance, the criterion used in [5], kH k 1 Gamma H k k p 2n, does not guarantee the convergence of the Newton Schulz iteration; kH k Gamma I 2n kkH k I 2n k 1 tends to switch too late, and kH 2 k Gamma I 2n k 1 is computationally too expensive. 17 4 Parallelization Issues and Performance Analysis Our parallel ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. Sci. Comput., 18:1446--1461, 1997.

....Examples arise in statistics [4, x7.5] 15, x2.3] 16, pp. 342] 3] in numerical integrations in superconductivity computations [11] and in stable subspace computation in control theory [18] The recent years have seen increasing interest in parallel solutions of large scale applications [2,3,7,14,10]. Inversion algorithms for general full nonsingular matrices are mostly based on the availability of a complete LU factorization. The algorithm used by Linpack xgedi [8] and Lapack xgetri [1] proceeds as follows. Departamento de Inform atica, Universidad Jaime I, 12071 Castell on, Spain, ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. on Scientific Computing, 18:1446--1461, 1997.

....subspaces. AMS subject classifications. 65F15, 47A75. 1. Introduction In the last years the matrix sign function has received a considerable attention as a divide and conquer method for obtaining complete or partial information about the eigenstructure of a matrix pencil (see, among others, [4, 5, 6, 15]) Given a matrix pair (A; B) A, B 2 C n Thetan , the matrix sign function can be used to obtain two unitary matrices, Q, Z 2 C n Thetan , such that Q h AZ = Q h 1 Q h 2 A (Z 1 ; Z 2 ) A 11 A 12 0 A 22 ; Q h BZ = Q h 1 Q h 2 B (Z 1 ; Z 2 ) B 11 B ....

Z. Bai, J. W. Demmel, J. Dongarra, A. Petitet, and H. Robinson, The spectral decomposition of nonsymmetric matrices on distributed memory multiprocessors, SIAM J. Sci. Comp., 18 (1997), pp. 1446--1461.

....QR algorithm and similar results should be expected from it. In this paper we revisit a spectral division method based on the generalized Newton iteration for the matrix sign function. Parallel implementations of the Newton iteration for the standard eigenproblem have been previously analyzed in [3]. The application of the generalized Newton iteration to a Hamiltonian eigenproblem has been studied, among others, in [10] Our renewed interest is motivated by a recent paper [22] that reports two improvements of this approach: a reduction of the cost of the generalized Newton iteration by 75 ....

Z. Bai, J. W. Demmel, J. Dongarra, A. Petitet, and H. Robinson. The spectral decomposition of nonsymmetric matrices on distributed memory multiprocessors. SIAM J. Sci. Comp., 18:1446--1461, 1997.

....attention; the survey [23] lists over 100 references. The rounding error analysis and perturbation theory are becoming understood [2, 12, 13, 14, 19, 32] Because they are rich in matrix matrix operations, matrix sign function algorithms are well suited to computers with advanced architectures [3, 1, 2, 9, 20, 21]. Its presence in the ScaLAPACK library [10] is an indication of its maturity and acceptance. The first matrix sign function algorithm for finding a deflating subspace was derived in [20] If E Gamma A is a square pencil with no infinite eigenvalue and no finite eigenvalue with zero real part, ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley, The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers, SIAM J. Sci. Comput., 18 (1997), pp. 1446--1461.

.... the matrices are cyclically distributed by blocks among a p r Theta p c mesh of processors; for scalability purposes, we only employ square topologies (p r = p c ) Our theoretical analysis of the parallel algorithms follows the performance model for the spectral division problem presented in [2]. The following problem and machine parameters are used: n: The dimension of the problem. p = p p Theta p p: The dimension of the mesh of processors. Cost of a flop. ff: Cost of transfering a void message between two processors. fi: Cost of transfering a floating point ....

Z. Bai et al. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers, SIAM J. Sci. Comp., 18 (1997), pp. 1446-- 1461.

....describe the techniques so that they can be easily customized for specific distributions. The library as it stands would be useful for implementation of a wide range of algorithms, including the LU factorization [21] the left looking Cholesky factorization, matrix multiplication based eigensolvers[6, 7, 8, 33], or out of core dense linear solvers [31] Finally, in [26] we show how this approach can be used for parallel implementation of Strassen s algorithm for matrix matrix multiplication. This suggests that an entire suite of variants of Strassen s algorithm for all the level 3 BLAS could be ....

Bai, Z., Demmel, J., Dongarra, J., Petitet, A., Robinson, H., Stanley, K., The Spectral Decomposition of Nonsymmetric Matrices on Distributed Memory Parallel Computers, LAPACK working note 91, University of Tennessee, Jan. 1995

....attracting much attention. The survey [19] lists over 100 references. The rounding error analysis and perturbation theory are becoming understood [2, 9, 10, 11, 13, 27] Because it is rich in matrixmatrix operations, the matrix sign function is well suited to computers with advanced architectures [1, 2, 3, 15, 23]. It has been demonstrated on matrices of order greater than 10,000 [1] A sign of its maturity and acceptance is its presence in the ScaLAPACK library [7] If A has no eigenvalue with zero real part, then sign(A) is defined and the Newton iteration A 0 = A A j 1 = 1 2 (A j A Gamma1 j ) ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley, The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers, SIAM J. Sci. Comput., 18 (1997), pp. 1446--1461.

....is poorly conditioned. There are inverse free iteration schemes for the matrix sign function, such as Newton Schulz iteration [14] at the expense of loosing global convergence. For more details on numerical computation and high performance implementation of the Newton iteration, see, for example, [4,5,6,8,19]. Malyshev presented an alternative scheme, see Figure 1, for the spectral division [18] Notice that there is no inverse involved in the iteration. We also note in passing that a singular pencil can be detected at the normalization step. The theoretical foundation of Malyshev s iteration is ....

Z. Bai, J. W. Demmel, J. Dongarra, A. Petitet, and H. Robinson. The spectral decomposition of nonsymmetric matrices on distributed memory multiprocessors. Technical Report CS-95-273, Computer Science Dept., University of Tennessee at Knoxville, 1995. to appear in SIAM J. Sci. Comp.

....of the various parts of the matrix during the decomposition process and make use of data and task parallelism. This approach has been investigated for the parallel implementation of the spectral divide and conquer algorithm for the unsymmetric eigenvalue problem using the matrix sign function [2]. We did not choose this approach because in the symmetric case the partitioning of the matrix can be done arbitrarily and we prefer to take advantage of this opportunity. By contrast with previous implementations we use a splitting different from the natural splitting associated with the binary ....

Zhaojun Bai, James W. Demmel, Jack J. Dongarra, Antoine Petitet, Howard Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. Sci. Comput., 18(5):1446--1461, 1997.

....the various parts of the matrix during the decomposition process and to make use of data and task parallelism. This approach has been investigated 1 for the parallel implementation of the spectral divide and conquer algorithm for the unsymmetric eigenvalue problem using the matrix sign function [2]. However, we did not choose this approach, because in the symmetric case the partitioning of the matrix can be done arbitrarily and we prefer to take advantage of this opportunity. As we use the two dimensional block cyclic distribution, it is now natural to partition the original problem into ....

Z. Bai, J. W. Demmel, J. J. Dongarra, A. Petitet, H. Robinson, and K. Stanley, The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers, SIAM J. Sci. Comput., 18 (1997), pp. 1446--1461.

....spectral decomposition problem is not ill conditioned, the algorithm is a practical approach to solve the nonsymmetric eigenvalue problem. Performance evaluation of the matrixsign function based algorithm on parallel distributed memory machines, such as the Intel Delta and CM 5, is reported in [4]. During the course of this work, we have discovered a new approach which essentially computes the same spectral projection matrix as the matrix sign function approach does, and also uses basic matrix operations, namely, matrix multiplication and the QR decomposition. However, it avoids the matrix ....

<F3.759e+05> Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K.<F3.851e+05> Stanley,<F3.469e+05> The spectral decomposition of nonsymmetric matrices on distributed memory parallel<F3.851e+05> computers, SIAM J. Sci. Comput., 18 (1997), pp. 1446--1461. <F4.498e+05>224<F3.851e+05> ZHAOJUN BAI AND JAMES DEMMEL

....of the various parts of the matrix during the decomposition process and make use of data and task parallelism. This approach has been investigated 1 for the parallel implementation of the spectral divide and conquer algorithm for the unsymmetric eigenvalue problem using the matrix sign function [2]. We did not choose this approach because in the symmetric case the partitioning of the matrix can be done arbitrarily and we prefer to take advantage of this opportunity. By contrast with previous implementations we use a splitting different from the natural splitting associated with the binary ....

Zhaojun Bai, James W. Demmel, Jack J. Dongarra, Antoine Petitet, Howard Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. Sci. Comput., 18(5):1446--1461, 1997.

....critical to any QR algorithm is blocked independently of the distributed block size. The application of the Householder reflections are also done in a block fashion (independent of the above broadcast blocking) to increase data re use. Our second algorithm is based on the sign function of a matrix [3, 4, 5]. This algorithm offers the flexibility of computing just part of the Schur form (corresponding, say, to the eigenvalues with positive real parts) uses more highly parallelized building blocks from ScaLAPACK than the HQR algorithm in the last paragraph (matrix inversion, matrix multiply and QR ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory computers. LAPACK Working Note #91 Technical report UT CS--95--273, University of Tennessee, 1995.

....spectral decomposition problem is not ill conditioned, the algorithm is a practical approach to solve the nonsymmetric eigenvalue problem. Performance evaluation of the matrix sign function based algorithm on parallel distributed memory machines, such as the Intel Delta and CM 5, is reported in [3]. During the course of this work, we have discovered a new approach which essentially computes the same spectral projection matrix as the matrix sign function approach does, 1 The permutation Pi can be avoided if we use the rank revealing QL decomposition. 22 and also uses basic matrix ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. Computer Science Department Techical Report CS-95-273, University of Tennessee at Knoxville, 1995. To appear in SIAM J. Sci. Comp.

....spectral decomposition problem is not ill conditioned, the algorithm is a practical approach to solve the nonsymmetric eigenvalue problem. Performance evaluation of the matrix sign function based algorithm on parallel distributed memory machines, such as the Intel Delta and CM 5, is reported in [4]. During the course of this work, we have discovered a new approach which essentially computes the same spectral projection matrix as the matrix sign function approach does, and also uses basic matrix operations, namely, matrix multiplication and the QR decomposition. However, it avoids the matrix ....

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. Computer 20 Z. BAI AND J. DEMMEL Science DepartmentTechical Report CS-95-273, University of Tennessee at Knoxville, 1995. To appear in SIAM J. Sci. Comp.

....task parallelism. This approach has been investigated 1 for the parallel implementation of the spectral divide and conquer algorithm for the unsymmetric eigenvalue problem using the 1 A ScaLAPACK prototype code is available at http: www.netlib.org scalapack prototype matrix sign function [2]. We did not choose this approach because in the symmetric case the partitioning of the matrix can be done arbitrarily and we prefer to take advantage of this opportunity. By contrast with previous implementations we use a splitting different from the natural splitting associated with the binary ....

Zhaojun Bai, James W. Demmel, Jack J. Dongarra, Antoine Petitet, Howard Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. Sci. Comput., 18(5):1446--1461, 1997.

....is highly parallel. Auslander and Tsao [2] and Lederman, Tsao, and Turnbull [36] use multiply based parallel algorithms based on matrix polynomials to split the spectrum. Bai and Demmel [4] use similar matrix multiply techniques using the matrix sign function to split the spectrum (see also [6, 10, 5, 7]. Dongarra and Sidani [17] introduced tearing methods based on doing rank one updates to an unsymmetric Hessenberg matrix, resulting in two smaller problems, which are solved independently and then glued back together with a Newton iteration. This tends to suffer from stability problems since the ....

Bai, Z., Demmel, J., Dongarra, J., Petitet, A., Robinson, H., Stanley, K., The Spectral Decomposition of Nonsymmetric Matrices on Distributed Memory Parallel Computers, LAPACK working note 91, University of Tennessee at Knoxville, Jan. 1995 To appear in SIAM Scientific Computing.

No context found.

Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM J. on Scientific Computing, 18:1446--1461, 1997.

Online articles have much greater impact   More about CiteSeer.IST at NUS   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.