Qize Zhang · Applied and Computational Engineering · 2024
This research mainly focuses on fast matrix multiplication algorithms. Fast matrix multiplication is one of the most fundamental problems in computer science. The fast matrix multiplication algorithm differs from conventional matrix multiplication in that it offers a faster computational approach that can perform the operation in less than O(n3) time complexity. This algorithm provides a more efficient method for multiplying matrices, significantly reducing the computational requirements. The Laser method, developed by Coppersmith and Winograd, is an algorithm for matrix multiplication that does not involve direct computation. It establishes a relationship between matrix multiplication and tensors and simplifies the operation by finding an intermediate tensor that is computationally manageable. This method applies a series of simplification operations to determine an upper bound on the computational complexity of matrix multiplication. However, as matrices become larger, the computational and memory requirements increase, posing challenges for practical implementation. This research will present the main ideas and performance of the Laser method and discuss the improvements made to the Laser method, including refined analysis and asymmetric hashing techniques. Additionally, it highlights the need for further exploration, such as parallel computing and optimization strategies, to enhance the efficiency of matrix multiplication algorithms. Furthermore, this research will also provide a prospectus for the future of matrix multiplication algorithms, such as the practical implementation of the Laser method.
Cited by 0Open access
Tang Yong · 2007
Modular exponentiation of large integers is having been the choke point for RSA.After analyzing traditional algorithms, a new fast modular exponentiation algorithm was presented.Wallace tree, lookup table and parallel multiplication were used in the algorithm.With theoretical analyzing and practical application, it was shown that the time complexity of the new algorithm was reduced to O(nlog n).
Cited by 0
Manoranjan Pradhan, Rutuparna Panda, Sushanta Kumar Sahu · International Journal of Computer Applications · 2011
The paper presents the implementation of MAC (multiplieraccumulator) unit using Vedic multiplier. The speed of MAC depends on the speed of the multiplier. The Vedic multiplier uses "Urdhva Tiryagbhyam" algorithm. The proposed MAC unit is coded in VHDL, synthesized and simulated using Xilinx ISE 10.1 software. The MAC is implemented on a FPGA device XC2S200-6PQ208 using Xilinx ISE10.1 tool. The proposed design shows improvement of speed over the design presented in
Cited by 8Open access
Carolyn L. Pinchback, D. S. Tomer · Mathematics Teacher Learning and Teaching PK-12 · 2002
The term Vedic mathematics usually refers to a set of sixteen word formulas, or sutras, along with their corollaries, that have origin in the Vedas. The Vedas are ancient holy texts from India that can be characterized as the allencompassing repository of Hindu knowledge from eons past. The Urdhva-tiryagbhyam sutra , or algorithm, has similarities to the FOIL (first, outer, inner, last) method that is used in algebra to multiply two binomials. We first illustrate this sutra with examples. Then we focus on similarities between Urdhva-tiryagbhyam and the standard multiplication algorithm, justifications for it, and student projects that relate to this algorithm.
Cited by 1
Stéphane Ballet, Robert Rolland · Journal of Algebra · 2003
Cited by 39
Elleithy, Khaled M., Bayoumi, Magdy A. · University of Bridgeport ScholarWorks (University of Bridgeport) · 2014
A θ(log n) algorithm for large moduli multiplication for Residue Number System (RNS) based architectures is proposed. The proposed modulo multiplier is much faster than previously proposed multipliers and more area efficient. The implementation of the multiplier is modular and is based on simple cells which leads to efficient VLSI realization. A VLSI implementation using 3 micron CMOS process shows that a pipelined n-bit modulo multiplication scheme can operate with a throughput of 30 M operation per second.
Cited by 0
S. Eijsvogel, Roeland J. Dilz, Martijn C. van Beurden · TU/e Research Portal · 2024
Optical scatterometry is a fast, non-destructive, and accurate technique for monitoring integrated circuits (ICs) for defects during their lithographic production process. The detection of these defects with potentially sub-wavelength size hinges on the accurate scattered electromagnetic fields as provided by a Maxwell solver. Generating this information typically induces a heavy computational workload. To this end, it is key to develop computationally efficient Maxwell solvers, to provide this information in a fast and accurate manner as a means to safeguard the production quality of ICs.
Cited by 0Open access
Hai Bin Zhang, Xiao Ping Ji, Bo Wu et al. · Applied Mechanics and Materials · 2013
Scalar point multiplication operation on elliptic curve is the most expensive part of the elliptic curve cryptosystem, also has always been the hot spot of the research. Recoding the positive integer and reducing the amount of inversion in the operation are the two main ideas. In this article, we use the balanced ternary form to recode the positive integer, at the same time, improve the part of calculation way of, reducing the amount of inversion, decreasing operation cost, and improving operation efficiency
Cited by 3
Baohua Zhang, Xinchun Yin · 2009
In this paper, we present a generic algorithm for evaluating the multiple of a point on an elliptic curve;or more generally, for computing an exponentiation in arbitrary Abelian group. Our algorithm uses a ternary representation for scalars and achieves both fast performance and resistivity against SPA attacks and safe error attacks. Moreover, our algorithm nicely works in parallel. Comparisons show that our proposed algorithm establishes a faster scalar multiplication. The most important observation is that our proposed algorithm makes greater improvements for Hessian form curve over fields of characteristic three than any other curves overlarge prime fields or binary fields.
Cited by 0
S. Roobini Priya, Prabhat Ranjan · Greater South Information System · 2022
Abstract This paper discusses on Vedic based floating point multiplication. The computations with integers representing very big or tiny numbers is cumbersome due to power aware designs required in IC designs. A good way to express integer values is using the IEEE 754 floating point encoding. DSP applications that use floating point numbers have a wide dynamic range of sophisticated computational processes that call for imprecise calculation techniques. This article describes the implementation and design of the Vedic multiplication and exact floating-point adder-based IEEE 754 channelized floating-point multiplier. The concepts in Vedic mathematics can be meritoriously used to improve logical sequences for implementing computational blocks in system on chip designs. Specific Vedic Sutras are discussed in this paper to implement and create the channelized floating-point multiplier according to IEEE 754. The multiplier's inputs are presented in IEEE 754 32-bit format. For mantissa multiplication, it uses the Urdhva Triyakbhyam sutra. Cases of underflow and overflow are handled through effective designs, to support design of pSoCs with power awareness.
Cited by 0Open access
Oleg Mazonka · arXiv (Cornell University) · 2022
This paper describes a sufficiently simple modular multiplication algorithm, which uses only carry-save addition with bit inspection Boolean logic and without number comparison or carry propagation.
Cited by 1Open access
Pawan Manoj Rathod, Ankit Bhupendra Vartak, Neha Kunte · 2018
With the bird's eye view of many analyst's attentions in the last few years to know how companies are collecting and transmitting enormous amounts of information. As there are problems in transmitting large amount of data. This is a need of an hour to overcome the problems. The data can be compress such as word file or image file etc. to send the data efficiently. Compression must be done in such a way that loss of data is minimum (i.e. 0%). Image compression helps to overcome the problem of sending large images. In this Discrete Cosine Transformation (DCT) plays a crucial role. In DCT, for compression of JPEG images we have techniques of Quantization and encoding. In this whole work, we have used Custom matrix multiplication algorithm (CMM) for reducing the complexity of matrix multiplication (MM) problem. The results from the experiment when comparing with Naive matrix multiplication and Strassen's matrix multiplication shows increase in the performance of DCT. As the performance have increased due to the less time and space complexity of Strassen's as compared to Naive. As CMM is having less time and space complexity as compared to Strassen's algorithm we are expecting to have more increase in performance. The time required for compression and the size of the files after compression with different algorithms for different images helps to differentiate between the performances.
Cited by 0
Juby Mathew, R Vijaya Kumar · 2012
The main focus of this paper is to compare the execution time complexity and space complexity between Strassen’s algorithm and the conventional algorithm for matrix multiplication. The aim is to design a program, which generates two matrices with various dimensions, and multiplies the two matrices using both the Strassen’s algorithm and the conventional algorithm. The execution time of each algorithm is recorded to evaluate the performance of each algorithm. The programming language used this project is Java. Some of the main achievements in this project are, successfully divide matrices into blocks, the Strassen’s algorithm was applied to each blocks recursively, and the level of recursion was controlled. The overall finding is that the Strassen’s algorithm is more efficient than conventional algorithm on large size of matrices. However, in scientific computing, memory has to be considered. The results show that Strassen’s algorithm needs more memory allocations than the conventional algorithm, due to the fact in design that more arrays need to be created.
Cited by 5
Rupali Verma, Maitreyee Dutta, Renu Vig · 2015
Modular multiplication is basic operation in public key cryptosystems like RSA. Montgomery modular multiplication being efficient is widely used. It is based on additions and shift operations. Each iteration requires a right shift, therefore in a word based architecture a complete word is not formed at end of iteration. This paper presents compute early word based scalable Montgomery architecture. It computes the most significant bit of word by applying 2 XOR operations. Also compute early scheme for common multiplicand Montgomery is proposed. Both the architectures are compared with previous architectures in literature.
Cited by 2
Mile Stojčev, E.I. Milovanović, I.Ž. Milovanović · Parallel Computing · 1990
Cited by 2
Maria Lapina, S. Neelakandan, Ivan Borodulin et al. · Lecture notes in networks and systems · 2024
Cited by 0
Joseph Ercolano · The Arithmetic Teacher · 1974
In the mathematics of finance, as well as in numerous engineering calculations, it often happens that one is required to perform the multiplication of two numbers, each of which contains a considerable number of digits to the right of the decimal point, and round off the product to a desired number of places (considerably fewer relative to the places appearing in the original numbers).
Cited by 1
V. Markova · 2002
A new multilayer cellular algorithm for complex number multiplication is presented. The upper estimate of the time complexity is obtained. The design is based on an original model of distributed computation which is called Parallel Substitution Algorithm.
Cited by 0
Deena P. Francis, Kumudha Raimond · Journal of King Saud University - Computer and Information Sciences · 2018
Approximate Matrix Multiplication (AMM) has emerged as a useful and computationally inexpensive substitute for actual multiplication of large matrices. Randomized as well as deterministic solutions to AMM were provided in the past. The latest work provides a deterministic algorithm that solves AMM more accurately than the other works. It is a streaming algorithm that is both fast and accurate. But, it is less robust to noise and is also liable to have less than optimal performance in the presence of concept drift in the input matrices. We propose an algorithm that is more accurate, robust to noise, invariant to concept drift in the data, while having almost the same running time as the state-of-the-art algorithm. We also prove that theoretical guarantees exist for the proposed algorithm. An empirical performance improvement of up to 90% is obtained over the previous algorithm. We also propose a general framework for parallelizing the proposed algorithm. The two parallelized versions of the algorithm achieve up to 1.9x and 3.6x speedups over the original version of the proposed algorithm.
Cited by 10Open access
Jinchuan Yang, S. He, Ming-Qiang Bai et al. · Journal of Physics A Mathematical and Theoretical · 2024
Abstract In quantum computing,
matrix multiplication occurs as a subroutine in more complex algorithms. 
We improve the quantum linear system algorithm 
[Harrow et al . 2009 Phys. Rev. Lett. 103 150502] 
to perform sparse matrix-matrix multiplication and propose a subroutine for parallel vector addition. 
Based on them, a quantum algorithm is exhibited for N × N positive matrix-positive matrix multiplication.
For some small ratio of the maximum element to the minimum element of the positive matrices (i.e., O (poly log N )), 
this algorithm achieves exponential acceleration.
Cited by 0