An Ultrafast Cellular Method for Matrix Multiplication

The author considers the ultrafast cellular method of matrix multiplication that deals with cellular submatrices, interacts with well-known matrix multiplication cellular methods, and minimizes by 12.5% the computing complexity of cellular analogs of well-known matrix multiplication algorithms generated on their basis. The interaction of the ultrafast cellular method with the unified cellular method of matrix multiplication provides the highest (as compared with well-known methods) percentage (equal to 45.2%) of minimization of multiplicative, additive, and overall complexities of well-known matrix multiplication algorithms. The computing complexity of the ultrafast method is estimated using the models of getting cellular analogs of the traditional matrix multiplication algorithm.     

A fast cellular method of matrix multiplication

This paper proposes a cellular method of matrix multiplication. The method reduces the multiplicative and additive complexities of well-known matrix multiplication algorithms by 12.5%. The computational complexities of cellular analogs of such algorithms are estimated. A fast cellular analog is presented whose multiplicative and additive complexities are equal to ≈0.382n³ multiplications and ≈1.147n³ additions, respectively, where n is the order of the matrices being multiplied. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 55–59, May–June 2008.     

A unified cellular method for matrix multiplication

A unified cellular method for matrix multiplication is proposed. The method is a hybrid of three methods, namely, Strassen’s and Laderman’s recursive methods and a fast cellular method for matrix multiplication. The interaction of these three methods provides the highest (in comparison with well-known methods) percentage (equal to 37%) of minimization of the multiplicative, additive, and overall complexities of cellular analogues of well-known matrix multiplication algorithms. The estimation of the computational complexity of the unified method is illustrated by an example of obtaining a cellular analogue of the traditional matrix multiplication algorithm.     

A mixed cellular method of matrix multiplication

A mixed cellular method of matrix multiplication is proposed that combines the Strassen method with a fast cellular method of matrix multiplication. The interaction of these methods makes it possible to decrease the multiplicative and additive complexities of well-known matrix multiplication algorithms by 25%. Estimates of computational complexity of cellular analogues of the mentioned algorithms are given. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 22–27, January–February 2009.     

New fast hybrid matrix multiplication algorithms

New hybrid algorithms are proposed for multiplying (n × n) matrices. They are based on Laderman’s algorithm for multiplying (3 × 3)-matrices. As compared with well-known hybrid matrix multiplication algorithms, the new algorithms are characterized by the minimum computational complexity. The multiplicative, additive, and overall complexities of the algorithms are estimated.     

Fast Multiplication and Sparse Structures

The applicability of fast multiplication algorithms to sparse structures is discussed. Estimates for the degree of sparseness of matrices and polynomials are given for which fast multiplication algorithms have advantages over standard multiplication algorithms in terms of the multiplicative complexity. Specifically, the Karatsuba and Strassen algorithms are studied under the assumption of the uniform distribution of zero elements.     

Fast hybrid matrix multiplication algorithms

New hybrid algorithms for matrix multiplication are proposed that have the lowest computational complexity in comparison with well-known matrix multiplication algorithms. Based on the proposed algorithms, efficient algorithms are developed for the basic operation \( D = C + \sum\limits_{l =1}^{\xi} A_{l} B_{l}\) of cellular methods of linear algebra, where A, B, and D are square matrices of cell size. The computational complexity of the proposed algorithms is estimated.     

Recursion based parallelization of exact dense linear algebra routines for Gaussian elimination

We present block algorithms and their implementation for the parallelization of sub-cubic Gaussian elimination on shared memory architectures. Contrarily to the classical cubic algorithms in parallel numerical linear algebra, we focus here on recursive algorithms and coarse grain parallelization. Indeed, sub-cubic matrix arithmetic can only be achieved through recursive algorithms making coarse grain block algorithms perform more efficiently than fine grain ones. This work is motivated by the design and implementation of dense linear algebra over a finite field, where fast matrix multiplication is used extensively and where costly modular reductions also advocate for coarse grain block decomposition. We incrementally build efficient kernels, for matrix multiplication first, then triangular system solving, on top of which a recursive PLUQ decomposition algorithm is built. We study the parallelization of these kernels using several algorithmic variants: either iterative or recursive and using different splitting strategies. Experiments show that recursive adaptive methods for matrix multiplication, hybrid recursive–iterative methods for triangular system solve and tile recursive versions of the PLUQ decomposition, together with various data mapping policies, provide the best performance on a 32 cores NUMA architecture. Overall, we show that the overhead of modular reductions is more than compensated by the fast linear algebra algorithms and that exact dense linear algebra matches the performance of full rank reference numerical software even in the presence of rank deficiencies.     

Efficient algorithms of local discrete wavelet transform with Haar-like bases

In this paper, two new fast algorithms for calculating a local discrete wavelet transform for a one-dimensional signal based on the example of Haar’s wavelet basis are presented and their computational complexities are evaluated. The algorithms are compared with each other and with well-known algorithms of fast wavelet transform. Employment recommendations are given for each algorithm presented. Among other things the preference domains of these algorithms are shown, i.e., the parameters of wavelet transform calculating problem are specified so that these algorithms are computationally efficient. Conclusions regarding the advantages of the recursive algorithm over the alternative one and over the well-known algorithm of the fast wavelet transform are reached using the analysis of algorithmic complexities as the base and with regard to additional possibilities of the recursive algorithm. The extension of the algorithms considered to a two-dimensional case is presented. Vasilii N. Kopenkov. Was born in 1978. He was graduated in Samara State Aerospace University in 2001. At present time he works as an assistant on chair of geoinformatics in SSAU and as a junior research assistant in Institute of Image Processing Systems RAS. Head interests: image processing, earth remote sensing data and pattern recognition, geoinformatic systems. Author of 17 publications, including 7 articles. Member of the Russian Association Pattern Recognition and Image Analysis.     

Fuzzy additive hybrid operators for network-based decision making

Evidence Aggregation Networks based on multiplicative fuzzy hybrid operators were introduced by Krishnapuram and Lee. They have been used for image segmentation, pattern recognition, and general multicriteria decision making. One of the drawbacks to these networks is that the training is complex and quite time consuming. In this article, we modify these aggregation networks to implement additive fuzzy hybrid connectives. We study the theoretical properties of two classes of such aggregation operators, one where the union and intersection components are based on multiplication, and the other where these components are derived from Yager connectives. These new networks have similar excellent properties such as backpropagation training and node interpretability for decision making under uncertainty as do their multiplicative precursors. They also have the advantage that training is easier since the derivatives of the additive hybrid operators are not as complex in form. the appropriate training algorithms are derived, and several examples given to illustrate the properties of the networks. © 1994 John Wiley & Sons, Inc.     

On combination of first order Strang's splitting and additive splitting for the solution of multi-dimensional convection diffusion problem

In this article we present a new splitting approach for the numerical solution of the multi-dimensional convection diffusion equations. The method combines additive and multiplicative splitting. In particular the method combines first order Strang's splitting, multiplicative splitting defined for splitting the convection and diffusion equation, and additive splitting defined in accordance with the spatial variables. The method not only reduces the linear (or nonlinear) original problem into a series of one-dimensional and one physical operator linear problems, but also enables us to compute these one-dimensional problems using parallel processors. The accuracy and stability of the new algorithm are investigated through the solution of different multi-dimensional convection diffusion model problems with scalar coefficients.     

Investigating the penalty reward calculus of software users and its impact on requirements prioritization

ContextThe current requirements engineering techniques for prioritization of software requirements implicitly assume that each user requirement will have an independent and symmetric impact on user satisfaction. For example, it is assumed that implementing a high priority user requirement will positively impact his satisfaction and not implementing a high priority user requirement will negatively impact his satisfaction. Further, the impacts of implementing multiple user requirements on his satisfaction are expected to be additive. But is this always the case?ObjectiveThis paper empirically examines whether the assumptions of symmetric and multiplicative impacts of user requirements on his satisfaction are valid. Further, the study assesses the relative efficacy of 5 methods of requirements prioritization in managing these effects as reflected by the user satisfaction with the prioritized requirement sets.MethodTo test for existence and mitigation of asymmetric effects an adaptation of the widely accepted PRCA (Penalty Reward Contrast Analysis) method was used for 5 requirements prioritization techniques. To test for existence and mitigation of multiplicative effects MHMR (Moderated Hierarchical Multiple Regression) a well-accepted technique for testing interaction effects was used.ResultsBoth asymmetric and multiplicative effects of software requirements on user satisfaction were observed for requirements prioritized using all 5 requirements prioritization methods raising questions about the efficacy of present day requirements prioritization techniques. Further, the results of the experiment led to proposing a new method for requirements prioritization for managing these effects.ConclusionThe study empirically demonstrates the complexities of prioritizing software requirements and calls for a new generation of methods to address them. Understanding and resolving these complexities will enable software providers to conserve resources by enabling them to parsimoniously selecting only those requirements for implementation in the software product that have maximum incremental impact on user satisfaction.     

Image Segmentation Using Some Piecewise Constant Level Set Methods with MBO Type of Projection

In this work, we are trying to propose fast algorithms for Mumford-Shah image segmentation using some recently proposed piecewise constant level set methods (PCLSM). Two variants of the PCLSM will be considered in this work. The first variant, which we call the binary level set method, needs a level set function which only takes values ±1 to identify the regions. The second variant only needs to use one piecewise constant level set function to identify arbitrary number of regions. For the Mumford-Shah image segmentation model with these new level set methods, one needs to minimize some smooth energy functionals under some constrains. A penalty method will be used to deal with the constraint. AOS (additive operator splitting) and MOS (multiplicative operator splitting) schemes will be used to solve the Euler-Lagrange equations for the minimization problems. By doing this, we obtain some algorithms which are essentially applying the MBO scheme for our segmentation models. Advantages and disadvantages are discussed for the proposed schemes. We acknowledge support from the Norwegian Research Council and IMS of the National University of Singapore.     

Complexity measures for matrix multiplication algorithms

A new class of algorithms for the computation of bilinear forms has been recently introduced [1, 3]. These algorithms approximate the result with an arbitrarily small error. Such approximate algorithms may have a multiplicative complexity smaller than exact ones. On the other hand any comparison between approximate and exact algorithms has to take into account the complexity-stability relations. In this paper some complexity measures for matrix multiplication algorithms are discussed and applied to the evaluation of exact and approximate algorithms. Multiplicative complexity is shown to remain a valid comparison test and the cost of approximation appears to be only a logarithmic factor.     

椭圆曲线密码中标量乘算法的改进方案

基于椭圆曲线密码，提出了一种快速标量乘算法。此算法通过引入有符号和无符号滑动窗口编码方法，大大减少了标量乘算法中费时的加法运算次数。经理论分析和实验结果表明，运用有符号滑动窗口编码方法比NAF算法和无符号窗口编码方法更有优势，可以使标量乘算法比通常的算法效率提高更多。并且给出了最佳滑动窗口的宽度。     

Adaptive linear discriminant analysis for online feature extraction

In this paper, we present new adaptive algorithms for the computation of the square root of the inverse covariance matrix. In contrast to the current similar methods, these new algorithms are obtained from an explicit cost function that is introduced for the first time. The new adaptive algorithms are used in a cascade form with a well-known adaptive principal component analysis to construct linear discriminant features. The adaptive nature and fast convergence rate of the new adaptive linear discriminant analysis algorithms make them appropriate for online pattern recognition applications. All adaptive algorithms discussed in this paper are trained simultaneously using a sequence of random data. Experimental results using the synthetic and real multiclass, multidimensional input data demonstrate the effectiveness of the new adaptive algorithms to extract the optimal features for the purpose of classification.     

RSA密码系统有效实现算法

本文提出了实现RSA算法的一种快速、适合于硬件实现的方案，在该方案中，我们作用加法链将求幂运算转化为求平方和乘法运算并大大降低了运算的次数，使用Montgomery算法将模N乘法转化为模R（基数）的算法，模R乘积的转化，以及使用一种新的数母加法器作为运算部件的基础。     

Fast and highly scalable parallel computations for fundamental matrix problems on distributed memory systems

We present fast and highly scalable parallel computations for a number of important and fundamental matrix problems on distributed memory systems (DMS). These problems include matrix multiplication, matrix chain product, and computing the powers, the inverse, the characteristic polynomial, the determinant, the rank, the Krylov matrix, and an LU- and a QR-factorization of a matrix, and solving linear systems of equations. Our highly scalable parallel computations for these problems are based on a highly scalable implementation of the fastest sequential matrix multiplication algorithm on DMS. We show that compared with the best known parallel time complexities on parallel random access machines (PRAM), the most powerful but unrealistic shared memory model of parallel computing, our parallel matrix computations achieve the same speeds on distributed memory parallel computers (DMPC), and have an extra polylog factor in the time complexities on DMS with hypercubic networks. Furthermore, our parallel matrix computations are fully scalable on DMPC and highly scalable over a wide range of system size on DMS with hypercubic networks. Such fast (in terms of parallel time complexity) and highly scalable (in terms of our definition of scalability) parallel matrix computations were rarely seen before on any distributed memory systems.     

Some new designs of 2-D array for matrix multiplication andtransitive closure

We present some new regular iterative algorithms for matrix multiplication and transitive closure. With these algorithms, by spacetime mapping the 2-D arrays with 2N-1 and upper bound [(3N-1)/2] execution times for matrix multiplication can be obtained. Meanwhile, we can derive a 2-D array with 4N-2 execution rime for transitive closure based on the sequential Warshall-Floyd algorithm. All these new 2-D arrays for matrix multiplication and transitive closure have the advantages of faster and more regular than other previous designs     

Detecting the number of 2-D harmonics in multiplicative and additive noise using enhanced matrix

This paper proposes a method for detecting the number of two-dimensional (2-D) harmonics in multiplicative and additive noise. We define an enhanced matrix using the generalized covariances of 2-D harmonics in multiplicative and additive noise and derive an inherent relation between the number of 2-D harmonics and the eigenvalues of the enhanced matrix. The number of 2-D harmonics in multiplicative and additive noise could be detected based on this special relation. The proposed method avoids the peaks searching and does not need any assumptions about the distribution and color of the multiplicative and additive noise. The computation complexity of the proposed method is analyzed. Simulations demonstrate the effectiveness of the proposed method.