Narrow Results

In this paper we report on our first experience with a portable, easily usable communication environment, 'Sciddle', for distributing computations over a homogeneous network of UNIX computers. We demonstrate the usefulness of the system with applications from linear algebra and quantum chemistry on a network of Ethernet-connected Sun workstations and of Internet-connected Cray supercomputers, respectively.

QR decomposition (QRD) is one of the most widely used numerical linear algebra (NLA) kernels in several signal processing applications. Its implementation has a considerable and an important impact on the system performance. As processor architectures continue to gain ground in the high-performance computing world, QRD algorithms have to be redesigned in order to take advantage of the architectural features on these new processors. However, in some processor architectures like very large instruction word (VLIW), compiler efficiency is not enough to make an effective use of available computational resources. This paper presents an efficient and optimized approach to implement Givens QRD in a low-power platform based on VLIW architecture. To overcome the compiler efficiency limits to parallelize the most of Givens arithmetic operations, we propose a low-level instruction scheme that could maximize the parallelism rate and minimize clock cycles. The key contributions of this work are as follows: (i) New parallel and fast version design of Givens algorithm based on the VLIW features (i.e., instruction-level parallelism (ILP) and data-level parallelism (DLP)) including the cache memory properties. (ii) Efficient data management approach to avoid cache misses and memory bank conflicts. Two DSP platforms C6678 and AK2H12 were used as targets for implementation. The introduced parallel QR implementation method achieves, in average, more than 12$\times$ and 6$\times$ speedups over the standard algorithm version and the optimized QR routine implementations, respectively. Compared to the state of the art, the proposed scheme implementation is at least 3.65 and 2.5 times faster than the recent CPU and DSP implementations, respectively.

The aim of this paper is to propose numerical models and methods for solving (n×n) linear equations, AX=b where parameters in the matrix A and the vector b are random and correlated. In case of a probabilistic b and a deterministic A, the amount of second order co-variances computation is equivalent to solving the (n×n) problem sequentially n times with additional efforts of performing a Cholesky factorization plus a symmetric matrix multiplication of size n×n while the complexity for kth order correlation can be proven to be O(n^k+1). For randomness in both A and b with an assumption of multidimensional Gaussian distribution, two systems of linear equations with size n²(n+1) and n(n+1)/2 are derived and can be solved sequentially to obtain the desired statistical parameters up to the second order of X. Both approaches are coded as Matlab M-files, complied and run to test their efficiency. For higher order correlation with non-Gaussian distribution, an approximation scheme is proposed. Two applications in optimization are discussed.

This paper presents an improved analysis of a structured dimension-reduction map called the subsampled randomized Hadamard transform. This argument demonstrates that the map preserves the Euclidean geometry of an entire subspace of vectors. The new proof is much simpler than previous approaches, and it offers — for the first time — optimal constants in the estimate on the number of dimensions required for the embedding.

The rooks problem on a rectangular board is studied in this paper. Inspiring from the rook polynomials, the concept of determinant of square matrices is extended suitably to non-square matrices. We also provide some applications for quasi-determinant of non-square matrices. Furthermore, our algorithms for the rooks problem on a rectangular board and the quasi-determinant of non-square matrices are presented.