Efficient computation of the permanent of a sparse matrix

Computation of the permanent of a general matrix is a hard problem. However, for a sparse matrix its permanent can be obtained. In this note an efficient method is described for computing the permanent of (0,l)-matrix. The method is based on the numerical structure of a matrix defined in Cushkov [4]. We outline a method with reduced computation efforts and show that, by application on five examples, the method significantly increases the computation speed.     

基于增广矩阵束方法的平面天线阵列综合

针对平面阵列的稀布优化问题,提出了一种基于增广矩阵束方法的减少阵元数目、求解阵元位置和设计幅度激励的优化方法。首先对期望平面阵的方向图进行采样并由采样点数据构造增广矩阵,对此矩阵进行奇异值(SVD)分解,确定在误差允许范围内所需的最小阵元数目;然后基于广义特征值分解分别计算两组特征值,并根据类ESPRIT算法对特征值进行配对;最后在最小二乘准则条件下根据正确的特征值对求解平面阵列的阵元位置和激励。仿真结果表明该算法具有较高的计算效率和数值精度。     

A processor-time-minimal systolic array for transitive closure

Using a directed acyclic graph (DAG) model of algorithms, the authors focus on processor-time-minimal multiprocessor schedules: time-minimal multiprocessor schedules that use as few processors as possible. The Kung, Lo, and Lewis (KLL) algorithm for computing the transitive closure of a relation over a set of n elements requires at least 5n-4 parallel steps. As originally reported. their systolic array comprises n² processing elements. It is shown that any time-minimal multiprocessor schedule of the KLL algorithm's dag needs at least n²/3 processing elements. Then a processor-time-minimal systolic array realizing the KLL dag is constructed. Its processing elements are organized as a cylindrically connected 2-D mesh, when n=0 mod 3. When n≠0 mod 3, the 2-D mesh is connected as a torus     

A unified systolic array for adaptive beamforming

We present a new algorithm and systolic array for adaptive beamforming. Our approach improves on McWhirter's pioneering work in two respects. First, our algorithm uses only orthogonal transformations and thus should have better numerical properties. Second, the algorithm can be implemented on one single p × p triangular array of programmable processors that offers a throughput of one residual element per cycle.     

Fast computation of the Smith form of a sparse integer matrix

We present a new probabilistic algorithm to compute the Smith normal form of a sparse integer matrix . The algorithm treats A as a “black box”—A is only used to compute matrix-vector products and we do not access individual entries in A directly. The algorithm requires about black box evaluations for word-sized primes p and , plus additional bit operations. For sparse matrices this represents a substantial improvement over previously known algorithms. The new algorithm suffers from no “fill-in” or intermediate value explosion, and uses very little additional space. We also present an asymptotically fast algorithm for dense matrices which requires about bit operations, where O(MM(m)) operations are sufficient to multiply two matrices over a field. Both algorithms are probabilistic of the Monte Carlo type — on any input they return the correct answer with a controllable, exponentially small probability of error. Received: March 9, 2000.     

An optimal parallel algorithm for sparse matrix bandwidth reduction on a linear array

A simple and efficient algorithm for the bandwidth reduction of sparse symmetric matrices is proposed. It involves column-row permutations and is well-suited to map onto the linear array topology of the SIMD architectures. The efficiency of the algorithm is compared with the other existing algorithms. The interconnectivity and the memory requirement of the linear array are discussed and the complexity of its layout area is derived. The parallel version of the algorithm mapped onto the linear array is then introduced and is explained with the help of an example. The optimality of the parallel algorithm is proved by deriving the time complexities of the algorithm on a single processor and the linear array.     

A processor-time-minimal systolic array for cubical mesh algorithms

Using a directed acyclic graph (DAG) model of algorithms, the paper focuses on time-minimal multiprocessor schedules that use as few processors as possible. Such a processor-time-minimal scheduling of an algorithm's DAG first is illustrated using a triangular shaped 2-D directed mesh (representing, for example, an algorithm for solving a triangular system of linear equations). Then, algorithms represented by an n×n×n directed mesh are investigated. This cubical directed mesh is fundamental; it represents the standard algorithm for computing matrix product as well as many other algorithms. Completion of the cubical mesh required 3n-2 steps. It is shown that the number of processing elements needed to achieve this time bound is at least [3n^2/4]. A systolic array for the cubical directed mesh is then presented. It completes the mesh using the minimum number of steps and exactly [3n ^2/4] processing elements it is processor-time-minimal. The systolic array's topology is that of a hexagonally shaped, cylindrically connected, 2-D directed mesh     

A bit-level systolic array for digital contour smoothing

Linear operators for digital contour smoothing are described. These operators are defined by circulant Toeplitz matrices and allow to smooth digital contours in the least-squares sense. They minimize the undersampling, digitizing and quantizing error and allow to calculate invariants, such as curvature, which are not possible to calculate without smoothing. A bit-level systolic array which is capable of realizing the proposed operator is described. This array is easy to implement in VLSI, because the array cells involved are very simple. Furthermore, the array is completely pipelined on the bit-level, so that it operates with a high clock frequency achieving very high throughputs.     

Learning short multivariate time series models through evolutionary and sparse matrix computation

Multivariate time series (MTS) data are widely available in different fields including medicine, finance, bioinformatics, science and engineering. Modelling MTS data accurately is important for many decision making activities. One area that has been largely overlooked so far is the particular type of time series where the data set consists of a large number of variables but with a small number of observations. In this paper we describe the development of a novel computational method based on Natural Computation and sparse matrices that bypasses the size restrictions of traditional statistical MTS methods, makes no distribution assumptions, and also locates the associated parameters. Extensive results are presented, where the proposed method is compared with both traditional statistical and heuristic search techniques and evaluated on a number of criteria. The results have implications for a wide range of applications involving the learning of short MTS models.     

A practical solution for a large sparse matrix

This paper describes a computational technique that was used for determining whether a certain matrix equation, Mx = b, had an exact solution. Here, M^T was a sparse 96,208 × 40,040 integer matrix. The approach is an appropriate alternative for certain matrices when memory constraints preclude using conventional techniques. The tools used are simple and their data structures well-suited for virtual memory computers. An important aspect of the method is to adopt different data structures to represent the matrix as the matrix changes over the course of the problem.     

A systolic array for the longest common subsequence problem

We introduce a linear systolic array for the Longest Common Subsequence (LCS, for short) problem. We first present an array of m identical cells which computes the length of an LCS of two strings of length m and n, respectively, in linear time (i.e., in time proportional to m + n). Then we show that, by extending any cell with the systolic stack introduced by Guibas and Liang (1982), a new array can be designed to recover an LCS in linear time.     

A systolic processor array for the quadrant interlocking elimination method

In this paper a systolic array is presented for the solution of linear equations occurring in scientific and engineering calculations. The new systolic array is based on the parallel Quadrant Interlocking Elimination method of Evans and Hadjidimos [1].     

The design and time analysis of a systolic array with asynchronous protocols for matrix multiplication

In this paper, we present new techniques for designing systolic arrays and asynchronous arrays for recursive algorithms. More specifically, we propose a systolic array with simple local interconnections for matrix multiplication which achieves optimal performance without having undesirable features such as preloading input data or global broadcasting. An asynchronous array for matrix multiplication which can speed up the total computation time significantly is also presented. The key component of the asynchronous array is a communication protocol which controls input data flow properly and efficiently. Finally, performance of the arrays is analyzed and a simulation using Occam programmed in a Transputer network is reported.     

Two-level pipelined systolic array for multidimensional convolution

This paper describes a systolic array for the computation of n-dimensional (nD) convolutions for any positive integer n. Systolic systems usually achieve high performance by allowing computations to be pipelined over a large array of processing elements. To achieve even higher performance, the systolic array described in this paper uses a second level of pipelining by allowing the processing elements themselves to be pipelined to an arbitrary degree.     

A sparse nonnegative matrix factorization technique for graph matching problems

Graph matching problem that incorporates pairwise constraints can be cast as an Integer Quadratic Programming (IQP). Since it is NP-hard, approximate methods are required. In this paper, a new approximate method based on nonnegative matrix factorization with sparse constraints is presented. Firstly, the graph matching is formulated as an optimization problem with nonnegative and sparse constraints, followed by an efficient algorithm to solve this constrained problem. Then, we show the strong relationship between the sparsity of the relaxation solution and its effectiveness for graph matching based on our model. A key benefit of our method is that the solution is sparse and thus can approximately impose the one-to-one mapping constraints in the optimization process naturally. Therefore, our method can approximate the original IQP problem more closely than other approximate methods. Extensive and comparative experimental results on both synthetic and real-world data demonstrate the effectiveness of our graph matching method.     

A sparse matrix scheme for the computer analysis of structures

Many matrix formulations of structural analyses involve matrices having a large proportion of zero elements. By storing only the non-zero elements of all matrices, machine store and time may be utilised effectively, making the simplest matrix formulations feasible as a method of computer solution even for fairly large frame problems. The method of operation of some sparse matrix routines written for use on the Atlas Computer is briefly described and their application to some frame problems is discussed. The term “searching factor” is introduced as a guide to the efficiency of sparse matrix routines.     

A generic systolic array building block for neural networks withon-chip learning

Neural networks require VLSI implementations for on-board systems. Size and real-time considerations show that on-chip learning is necessary for a large range of applications. A flexible digital design is preferred here to more compact analog or optical realizations. As opposed to many current implementations, the two-dimensional systolic array system presented is an attempt to define a novel computer architecture inspired by neurobiology. It is composed of generic building blocks for basic operations rather than predefined neural models. A full custom VLSI design of a first prototype has demonstrated the efficacy of this design. A complete board dedicated to Hopfield's model has been designed using these building blocks. Beyond the very specific application presented, the underlying principles can be used for designing efficient hardware for most neural network models.     

Using underapproximations for sparse nonnegative matrix factorization

Nonnegative matrix factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc.We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs.We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard sparse nonnegative matrix factorization techniques.