A Jacobi-type method for computing balanced realizations

A new numerical scheme for computing balancing coordinate transformations in linear systems theory is presented. The method is closely related to the Jacobi method for diagonalizing symmetric matrices. Here the minimization of the sum of traces of the Gramians by orthogonal and nonorthogonal Jacobi-type rotations is considered. The algorithm is shown to be globally convergent to a balancing transformation that arranges the Hankel singular values in a prescribed ordering. Local quadratic convergence of the algorithm is shown.     

The real two-zero algorithm: a parallel algorithm to reduce a realmatrix to a real Schur form

We introduce a new method to reduce a real matrix to a real Schur form by a sequence of similarity transformations that are 3D orthogonal transformations. Two significant features of this method are that: all the transformed matrices and all the computations are done in the real field; and it can be easily parallelized. We call the algorithm that uses this method the real two-zero (RTZ) algorithm. We describe both serial and parallel implementations of the RTZ algorithm. Our tests indicate that the rate of convergence to a real Schur form is quadratic for real near-normal matrices with real distinct eigenvalues. Suppose n is the order of a real matrix A. In order to choose a sequence of 3D orthogonal transformations on A, we need to determine some ordering on triples in T={(k,l,m)|1⩽k相似文献   

A parallel method for computing the generalized singular value decomposition

We describe a new parallel algorithm for computing the generalized singular value decomposition of two n × n matrices, one of which is nonsingular. Our procedure requires O(n) time and one triangular array of O(n²) processors.     

Parallel block tridiagonalization of real symmetric matrices

Two parallel block tridiagonalization algorithms and implementations for dense real symmetric matrices are presented. Block tridiagonalization is a critical pre-processing step for the block tridiagonal divide-and-conquer algorithm for computing eigensystems and is useful for many algorithms desiring the efficiencies of block structure in matrices. For an “effectively” sparse matrix, which frequently results from applications with strong locality properties, a heuristic parallel algorithm is used to transform it into a block tridiagonal matrix such that the eigenvalue errors remain bounded by some prescribed accuracy tolerance. For a dense matrix without any usable structure, orthogonal transformations are used to reduce it to block tridiagonal form using mostly level 3 BLAS operations. Numerical experiments show that block tridiagonal structure obtained from this algorithm directly affects the computational complexity of the parallel block tridiagonal divide-and-conquer eigensolver. Reduction to block tridiagonal form provides significantly lower execution times, as well as memory traffic and communication cost, over the traditional reduction to tridiagonal form for eigensystem computations.     

Zur Berechnung von Lösungen konsistenter linearer Gleichungssysteme mit singulärer Koeffizientenmatrix

Based on a roundoff error analysis, it is shown how to modify the well-known iterative refinement algorithm for nonsingular linear algebraic systems to get an algorithm for computing one of the solutions of a consistent system with quadratic singular matrix. The algorithm is given explicitly for symmetric matrices.     

Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms

An algorithm is presented in this paper for computing state-space balancing transformations directly from a state-space realization. The algorithm requires no "squaring up" or unnecessary matrix products. Various algorithmic aspects are discussed in detail. A key feature of the algorithm is the determination of a contragredient transformation through computing the singular value decomposition of a certain product of matrices without explicitly forming the product. Other contragredient transformation applications are also described. It is further shown that a similar approach may be taken, involving the generalized singular value decomposition, to the classical simultaneous diagonalization problem. These SVD-based simultaneous diagonalization algorithms provide a computational alternative to existing methods for solving certain classes of symmetric positive definite generalized eigenvalue problems.     

A Methodology for Mapping and Partitioning Arbitrary N-Dimensional Nested Loops into 2-Dimensional VLSI Arrays

A new methodology is proposed for mapping and partitioning arbitrary n-dimensional nested loop algorithms into 2-dimensional fixed size systolic arrays.Since planar VLSI arrays are easy to implement,our approach has good feasibility and applicability.In the transformation process of an algorithm,we take into account not only data dependencies imposed by the original algorithm but also space dependencies dictated by the algorithm ransformation,Thus,any VLSI algorithm generated by our methodology has optimal parallel execution time and yet remains space-time conflict free.Moreover,a theory of the least complete set of interconnection matrices is proposed to reduce the computational complexity for finding all possible space transformations for a given algorithm.     

An algorithm for pole assignment in high order multivariablesystems

An efficient computational method is presented for solving the problem of pole assignment by state feedback in linear multivariable systems with large dimensions. A given multiinput system is first transformed to an upper block Hessenberg form by means of orthogonal state coordinate transformations. The state feedback problem is then reformulated in terms of the Sylvester equation. The transformed system matrices, along with certain assumed block forms for unknown matrices, enable the Sylvester equation to be decomposed and solved effectively. A distinct point of the proposed algorithm is that the solution procedure can be tailored to parallel implementation and is therefore fast. Computational aspects of the algorithm are discussed and numerical examples are provided     

计算Arnold变换周期的新算法

Arnold变换的周期在图像置乱、图像水印和信息隐藏中具有重要的应用。为了更有效地进行图像置乱等操作,同时,为了进行Arnold变换在图像置乱等安全性的研究,需要更深入和全面地研究Arnold变换的周期及其规律性。为寻找更快地计算Arnold变换周期的新算法,应用迭代Arnold变换矩阵与Fibonaeei序列之间的关系,建立了通过Fihonaeci数特征计算Amdd周期的定理。根据该定理,提出了快速计算Arnold变换周期的新算法。实验结果表明,新算法与原算法相比在计算Arnold变换周期方面,速度有了很大提高。因此,新算法适用于快速计算Arnold变换的周期和用于图像置乱等操作。另一方面,所建立的定理在理论上也是有价值的。     

Parallel and sequential transformations on digital images

In this paper, the relation between parallel and sequential algorithms is discussed. We regard algorithms as definitions of transformations and investigated the relation between the sets of transformations defined by parallel and sequential algorithms. Three problems are treated mainly. The problems and the results for the problems may be summarized as follows. (1) Characterization of transformations which are both parallel and sequential—A necessary and sufficient condition for a transformation to be both parallel and sequential has been established. (2) Equivalence problems—The equivalence problem for two algorithms, one of which is parallel, is decidable, hence, the equivalence problem for two sequential algorithms is undecidable, i.e. an algorithm for deciding whether or not two given algorithms, one of which is parallel, define the same transformation has been presented. However, we have shown there is no algorithm for deciding whether or not two given sequential algorithms define the same transformation. (3) Translation problems—An algorithm for translating a parallel (sequential) algorithm into an equivalent sequential (parallel) algorithm has been presented.     

SIMD-BF模型上的并行FWHT算法研究

蝶形网络是并行计算中的一种重要的网络拓扑结构.并行计算模型是并行算法设计和分析的基础.文章以并行FFT算法的基本思想为基础,根据快速Walsh-Hadamard变换的两种蝶式计算流图,提出SIMD-BF模型上的两种并行FWHT算法.算法分析的结果表明:离散Walsh-Hadamard变换算法的复杂度为O(n2);快速W...     

A new version of the Chang transformation

A new decoupling transformation is proposed for singularly perturbed linear systems. This transformation has the advantage over the previous one in that, in order to find such a transformation, only one algorithm is required, and the computation can be done in parallel, because the transformation matrices are obtained from two independent equations that are identical in form     

A linear algebra framework for automatic determination of optimaldata layouts

This paper presents a data layout optimization technique for sequential and parallel programs based on the theory of hyperplanes from linear algebra. Given a program, our framework automatically determines suitable memory layouts that can be expressed by hyperplanes for each array that is referenced. We discuss the cases where data transformations are preferable to loop transformations and show that under certain conditions a loop nest can be optimized for perfect spatial locality by using data transformations. We argue that data transformations can also optimize spatial locality for some arrays without distorting temporal/spatial locality exhibited by others. We divide the problem of optimizing data layout into two independent subproblems: 1) determining optimal static data layouts, and 2) determining data transformation matrices to implement the optimal layouts. By postponing the determination of the transformation matrix to the last stage, our method can be adapted to compilers with different default layouts. We then present an algorithm that considers optimizing parallelism and spatial locality simultaneously. Our results on eight programs on two distributed shared-memory multiprocessors, the Convex Exemplar SPP-2000 and the SGI Origin 2000, show that the layout optimizations are effective in optimizing spatial locality and parallelism     

Efficient Algorithms for the Block Hessenberg Form

We investigate in this paper the performance of parallel algorithms for computing the controllable part of a control linear system, with application to the computation of minimal realizations. Our approach is based on a method that transforms the matrices of the system to block Hessenberg form by using rank-revealing orthogonal factorizations.The experimental analysis on a high performance architecture includes two rank-revealing numerical tools: the SVD and the rank-revealing QR factorizations. Results are also reported, using the rank-revealing QR factorizations, on a parallel distributed architecture.     

求对称方阵特征值的一种快速并行算法

该文针对经典雅可比算法求对称矩阵特征值不但要选主元素,而且还要同时进行行、列旋转变换、数据相关关系复杂、额外计算开销大、不易并行的缺点,提出了一种基于矩阵单侧旋转的算法并对此算法进行分析。最后通过该算法在PC机和分布式存储的大规模并行处理机曙光1000上的实验数据对比验证了该算法的性能较雅可比算法优越。     

Solving the generalized eigenvalue problem on a synchronous linear processor array

We present a parallel method to solve the generalized eigenvalue problem on a linear array of processors, each connected to their nearest neighbors and operating synchronously. We also include a wrap-around connection from end to end. Our method is based on the well-known QZ algorithm of Moler and Stewart, which simultaneously reduces two n × n matrices to upper triangular form by orthogonal or unitary transformations. We show how this algorithm may be partitioned and distributed of n + 1 processors, achieving a speed-up over the serial algorithm of O(n). We use the concept of windows to describe the action of each processor at each step. We show how to incorporate singles shifts, and how to apply orthogonal plane rotations on either side of a matrix without the need to transpose the matrix itself.     

A new block algorithm for full-rank solution of the Sylvester-observer equation

A new block algorithm for computing a full rank solution of the Sylvester-observer equation arising in state estimation is proposed. The major computational kernels of this algorithm are: 1) solutions of standard Sylvester equations, in each case of which one of the matrices is of much smaller order than that of the system matrix and (furthermore, this small matrix can be chosen arbitrarily), and 2) orthogonal reduction of small order matrices. There are numerically stable algorithms for performing these tasks including the Krylov-subspace methods for solving large and sparse Sylvester equations. The proposed algorithm is also rich in Level 3 Basic Linear Algebra Subroutine (BLAS-3) computations and is thus suitable for high performance computing. Furthermore, the results on numerical experiments on some benchmark examples show that the algorithm has better accuracy than that of some of the existing block algorithms for this problem.     

Computing distance transformations in convex and non-convex domains

It is shown that the well known two-pass sequential local transformation algorithm for computing a distance transformation in rectangular domains may fail in some convex integer domains, but that a four-pass algorithm is sufficient in all two-dimensional convex domains. For non-convex domains the number of passes necessary is shown to be generally greater. Two propagation algorithms for computing the distance transformation are described and shown theoretically and experimentally to be computationally more efficient than the sequential local transformation algorithm in non-convex domains of complex shape. The relationship of the distance transformation in non-convex domains to some more general transformations is explored.     

基于Walsh变换的数字水印算法*

经对目前数字水印变换域算法的研究,发现常用的变换大多都是正交变换（如DCT和DWT等）。通过对Walsh正交函数系的研究,获得了与之对应的性能优良的正交变换,提出一种新颖的、鲁棒的Walsh域盲水印算法。实验表明,该算法计算简单,且具有良好的不可见性,并且在抵抗噪声和JPEG压缩攻击等方面具有较强的鲁棒性。