The motivation of the present work concerns two objectives. Firstly, a predictor-corrector iterative method of convergence order p=45 requiring 10 matrix by matrix multiplications per iteration is proposed for computi...
详细信息
The motivation of the present work concerns two objectives. Firstly, a predictor-corrector iterative method of convergence order p=45 requiring 10 matrix by matrix multiplications per iteration is proposed for computing the Moore-Penrose inverse of a nonzero matrix of rank=r. Convergence and a priori error analysis of the proposed method are given. Secondly, the numerical solution to the general linear least squares problems by an algorithm using the proposed method and the perturbation error analysis are provided. Furthermore, experiments are conducted on the ill-posed problem of one-dimensional image restoration and on some test problems from Harwell-Boeing collection. Obtained numerical results show the applicability, stability, and the estimated order of convergence of the proposed method.
The aim of this work is to solve the image retrieval problems with modern methods of numerical linear algebra, which can be easily parallelized for distributed memory architectures like a cluster platform. Algorithm p...
详细信息
ISBN:
(纸本)9781905088423
The aim of this work is to solve the image retrieval problems with modern methods of numerical linear algebra, which can be easily parallelized for distributed memory architectures like a cluster platform. Algorithm presented in this paper is singular value decomposition (SVD). We show that SVD is directly linked with information retrieval through latent semantic indexing. However, our main concern is efficiency of computations of SVD. We present our parallel implementation of Householder bidiagonalization, which we consider the most computationally demanding step of singular value decomposition. We shall also compare our proposed algorithms with commonly used approaches on the experiments, and we shall emphasize their advatages in sence of usage of standard optimized linear algebra packages.
The Apriori algorithm needs to continue scanning the database and may provide mass candidate itemsets in fault diagnosis process which causes the mining speed too slow and the computer memory too large. According to t...
详细信息
ISBN:
(纸本)9783037852132
The Apriori algorithm needs to continue scanning the database and may provide mass candidate itemsets in fault diagnosis process which causes the mining speed too slow and the computer memory too large. According to these weaknesses this paper presents the bitmap-base association rule optimization algorithm (BARO). The BARO improves the data structure to reduce the scanning frequency of database and compresses the matrix to reduce the quantity of candidate itemsets in order to improve the speed of equipment fault diagnosis. It proves that BARO is superior to Apriori algorithm in equipment fault diagnosis of efficiency and mining speed by a concrete example.
We extend classical basis constructions from Fourier analysis to attractors for affine iterated function systems (IFSs). This is of interest since these attractors have fractal features, e.g., measures with fractal sc...
详细信息
We extend classical basis constructions from Fourier analysis to attractors for affine iterated function systems (IFSs). This is of interest since these attractors have fractal features, e.g., measures with fractal scaling dimension. Moreover, the spectrum is then typically quasi-periodic, but non-periodic, i.e., the spectrum is a "small perturbation" of a lattice. Due to earlier research on IFSs, there are known results on certain classes of spectral duality-pairs, also called spectral pairs or spectral measures. It is known that some duality pairs are associated with complex Hadamard matrices. However, not all IFSs X admit spectral duality. When X is given, we identify geometric conditions on X for the existence of a Fourier spectrum, serving as the second part in a spectral pair. We show how these spectral pairs compose, and we characterize the decompositions in terms of atoms. The decompositions refer to tensor product factorizations for associated complex Hadamard matrices.
Real-time signal processing and control applications are commonly expressed in terms of matrix or vector algorithms. This paper presents a novel decoupled architecture for these algorithms. The matrix data management ...
详细信息
ISBN:
(纸本)9780819465221
Real-time signal processing and control applications are commonly expressed in terms of matrix or vector algorithms. This paper presents a novel decoupled architecture for these algorithms. The matrix data management layer (MDML) architecture presented separates data processing from data management. It implements functions for memory sequencing and inter-processor communications that are tuned for matrix applications. This separation allows greater flexibility in the choice of data processor to find a suitable trade-off in speed, core size, power consumption and functionality.
matrix algorithms are important in many types of applications including image and signal processing. These areas require enormous computing power. A close examination of the algorithms used in these, and related, appl...
详细信息
ISBN:
(纸本)0819446580
matrix algorithms are important in many types of applications including image and signal processing. These areas require enormous computing power. A close examination of the algorithms used in these, and related, applications reveals that many of the fundamental actions involve matrix operations such as matrix multiplication which is of 0 (N-3) on a sequential computer and 0 (N-3/p) on a parallel system with p processors complexity. This paper presents an investigation into the design and implementation of different matrix algorithms such as matrix operations, matrix transforms and matrix decompositions using an FPGA based environment. Solutions for the problem of processing large matrices have been proposed. The proposed system architectures are scalable, modular and require less area and time complexity with reduced latency when compared with existing structures.
We consider the problem of approximating a given m x n matrix A by another matrix of specified rank k, which is smaller than in and n. The Singular Value Decomposition (SVD) can be used to find the "best" su...
详细信息
We consider the problem of approximating a given m x n matrix A by another matrix of specified rank k, which is smaller than in and n. The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in m, n which is prohibitive for some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find the description of a matrix D* of rank at most k so that [GRAPHICS] holds with probability at least 1 - delta (where parallel *** to(F) is the Frobenius norm). The algorithm takes time polynomial in k, 1/epsilon, log(1/delta) only and is independent of m and n. In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation.
This book is the second volume in a projected five-volume survey of numerical linear algebra and matrix algorithms. This volume treats the numerical solution of dense and large-scale eigenvalue problems with an emphas...
详细信息
ISBN:
(数字)9780898718058
ISBN:
(纸本)9780898715033
This book is the second volume in a projected five-volume survey of numerical linear algebra and matrix algorithms. This volume treats the numerical solution of dense and large-scale eigenvalue problems with an emphasis on algorithms and the theoretical background required to understand them. Stressing depth over breadth, Professor Stewart treats the derivation and implementation of the more important algorithms in detail. The notes and references sections contain pointers to other methods along with historical comments. The book is divided into two parts: dense eigenproblems and large eigenproblems. The first part gives a full treatment of the widely used QR algorithm, which is then applied to the solution of generalized eigenproblems and the computation of the singular value decomposition. The second part treats Krylov sequence methods such as the Lanczos and Arnoldi algorithms and presents a new treatment of the Jacobi-Davidson method. The volumes in this survey are not intended to be encyclopedic. By treating carefully selected topics in depth, each volume gives the reader the theoretical and practical background to read the research literature and implement or modify new algorithms. The algorithms treated are illustrated by pseudocode that has been tested in MATLAB implementations.
This paper describes the results of a project to interface MATLAB with a parallel virtual processor (PVP) that allows execution of matrix operations in MATLAB on a set of computers connected by a network. The software...
详细信息
This paper describes the results of a project to interface MATLAB with a parallel virtual processor (PVP) that allows execution of matrix operations in MATLAB on a set of computers connected by a network. The software, a connection-oriented BSD socket-based client-server model, automatically partitions a MATLAB problem and delegates work to server processes running on separate remote machines. Experimental data on the matrix multiply operation shows that the speed improvement of the parallel implementation over the single-processor MATLAB algorithm depends on the size of the matrices, the number of processes, the speed of the processors, and the speed of the network connection. In particular, the advantage of doing matrix multiply in parallel increases as the size of the matrices increase. A speedup of 2.95 times was achieved in multiplying 2048 by 2048 square matrices using 15 workstations. The algorithm was also implemented on a network of four PC's, which was up to 2.5 times as fast as four workstations. The study also showed that there is an optimal number of processes for a particular problem, and so using more processes is not always faster. (C) 2001 Elsevier Science Inc. All rights reserved.
In this paper, we discuss the use of binary decision diagrams to represent general matrices. We demonstrate that binary decision diagrams are an efficient representation for every special-case matrix in common use, no...
详细信息
In this paper, we discuss the use of binary decision diagrams to represent general matrices. We demonstrate that binary decision diagrams are an efficient representation for every special-case matrix in common use, notably sparse matrices. In particular, we demonstrate that for any matrix, the BDD representation can be no larger than the corresponding sparse-matrix representation. Further, the BDD representation is often smaller than any other conventional special-case representation: for the n x n Walsh matrix, for example, the BDD representation is of size O (log n). No other special-case representation in common use represents this matrix in space less than O (n(2)). We describe termwise, row, column, block, and diagonal selection over these matrices, standard an Strassen matrix multiplication, and LU factorization. We demonstrate that the complexity of each of these operations over the BDD representation is no greater than that over any standard representation. Further, we demonstrate that complete pivoting is no more difficult over these matrices than partial pivoting. Finally, we consider an example, the Walsh Spectrum of a Boolean function.
暂无评论