Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.
About 8,077 papers for “Multiplication algorithm”
Zhongde Wang, G.A. Jullien, William C. Miller · 2002
This paper proposes an efficient algorithm for multiplication modulo (2/sup N/-1). To achieve high speed, the Wallace tree is adopted for the multiplier. The Wallace tree multiplier exhibits a more regular structure than binary Wallace tree multipliers, and comparisons with published designs demonstrates advantages of our multiplier architecture in both speed and hardware.
Cited by 53
Huacheng Yu · Information and Computation · 2018
Cited by 21
Yihan Wang, Xiangjun Xue, Jingyong Liang et al. · 2025
People have a hard time using cloud computing because of rules concerning privacy and security in fields like healthcare and banking. Fully Homomorphic Encryption (FHE) lets computers work with encrypted data, but it puts a lot of burden on them. This paper introduces SMMHE (Secure Matrix Multiplication with FHE), a novel element-wise approach that enhances SIMD parallelism in contemporary FHE frameworks to mitigate costly rotation operations. SMMHE is 3.98× faster than the most common FHE-based multiplication techniques, according to thorough testing. This big speedup, which cuts the difference in performance between encrypted and plaintext computation by a lot, makes it much easier to use privacy-preserving cloud applications in real life, like classifying medical images. For encrypted MNIST classification, the amortized duration of 26 ms per image is an excellent example of this.
Cited by 0
Koca, Zuhal · DergiPark (Istanbul University) · 2020
Cited by 0Open access
Rusdi Md. Aminuddin, Rosni Abdullah, Suhaidi Hassan · Universiti Utara Malaysia Institutional Repository (Universiti Utara Malaysia) · 2004
Matrix multiplication is one of the important operations in scientific and engineering application. However, it is also one of the operations that are time consuming. Continuous researches have been conducted to improve this operation. One of the alternatives is to have the operation performed in parallel. However, these types of algorithms often carried out on expensive supercomputers or multiprocessing systems. With the advancement of personal computers and networking, the use of network of computers has become an advantage to the computing community. Although programming in such environment is relatively harder compared to that of in shared memory multiprocessing environment, its advantages outweigh its complexity. In this paper, we introduce the concept of Network of Computers (NOW) or Cluster computing and present its advantages. We discuss matrix-multiplication algorithm and highlight one of the parallel matrix--multiplication algorithms. We present the comparison in terms of speed between serial algorithm and the parallel algorithm when we run them on our cluster. We end our discussion by outlining our future works.
Cited by 0Open access
Aleksandr Cariow, Galina Cariowa · Advances in Applied Clifford Algebras · 2014
In this paper we introduce an efficient algorithm for the multiplication of Pauli numbers. The direct multiplication of two Pauli numbers requires 64 real multiplications and 56 real additions. More effective solutions still do not exist. We show how to compute a product of the Pauli numbers with 24 conventional multiplications, 8 multiplications by 1/2 and 56 real additions.
Cited by 6Open access
Sivanagireddy Kalli, S. Chamandi Priya · Lecture notes in electrical engineering · 2025
Cited by 0
John S. Garavelli · ACM Transactions on Mathematical Software · 1988
Although the cycle index polynomial for a permutation group can often be easily determined, expansion of the figure counting series in a Po´lya enumeration presents computational difficulties for object sets with higher degrees of symmetry and more than modest size. An algorithm that does not require algebraic symbol manipulation is derived for multiplying symmetric polynomials represented by partitions. Because the repetitive identification and collection of common terms are eliminated and storage requirements reduced, this algorithm is useful in rapidly expanding the figure counting series in such Po´lya enumeration problems as the counting of chemical isomers.
Cited by 1Open access
B. Hendrickson, R.P. Leland, S. Plimpton · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1993
The multiplication of a vector by a matrix is the kernel computation of many algorithms in scientific computation. A fast parallel algorithm for this calculation is therefore necessary if one is to make full use of the new generation of parallel supercomputers. This paper presents a high performance, parallel matrix-vector multiplication algorithm that is particularly well suited to hypercube multiprocessors. For an n x n matrix on p processors, the communication cost of this algorithm is O(n/[radical]p + log(p)), independent of the matrix sparsity pattern. The performance of the algorithm is demonstrated by employing it as the kernel in the well-known NAS conjugate gradient benchmark, where a run time of 6.09 seconds was observed. This is the best published performance on this benchmark achieved to date using a massively parallel supercomputer.
Cited by 4Open access
Dharamvir Kumar, Manoranjan Pradhan, Neeraj Kumar Misra et al. · Facta universitatis - series Electronics and Energetics · 2026
This paper introduces a novel architecture for signed multiplication, representing a significant advancement in VLSI design for high-end computation. We have implemented signed number multiplier numbers using the Urdhva Tiryagbhyam (UT) algorithm. The purpose of the proposed architecture is to overcome the limitations of previous approaches, through the integration of Virtex-7 and Spartan-7 hardware, in addition to improving power and delay performance. As a result of using vertical and crosswise techniques, the proposed parallel multiplication scheme for signed numbers is implemented in this paper. We have synthesized and simulated this structure using Vivado 2020.1 software and Virtex-7 and Spartan-7 FPGA devices for low-power VLSI computational applications, such as checking the speed and delay of the design postlayout. A comparison is made between the proposed design and existing architectures in terms of area, delay, and power consumption. According to the results, the proposed architecture improves speed by 40% over prior architectures. For faster computing applications, a high-speed proposed multiplier will be useful for complex design architecture. The work contributes significantly to the improvement of high-performance computing and digital signal processing.
Cited by 0Open access
J.A. Bergstra, C.A. Middelburg · UvA-DARE (University of Amsterdam) · 2013
The Karatsuba multiplication algorithm is an algorithm for computing the product of two natural numbers represented in the binary number system. This means that the algorithm actually computes a function on bit strings. The restriction of this function to bit strings of any given length can be computed according to the Karatsuba multiplication algorithm by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We describe the instruction sequences concerned for the restrictions to bit strings of the different lengths by uniform terms from an algebraic theory.
Cited by 4Open access
André Weimerskirch, Christof Paar · 2007
In this work we generalize the classical Karatsuba Algorithm (KA) for polynomial multiplication to (i) polynomials of arbitrary degree and (ii) recursive use. We determine exact complexity expressions for the KA and focus on how to use it with the least number of operations. We develop a rule for the optimum order of steps if the KA is used recursively. We show how the usage of dummy coefficients may improve performance. Finally we provide detailed information on how to use the KA with least cost, and also provide tables that describe the best possible usage of the KA for polynomials up to a degree of 127.
Cited by 0
Satnam S. Dlay, Raouf N. G. Naguib · 2014
Abstract:- This paper presents a simple algorithm for the evaluation of modular multiplication and division, which can be used in a number of applications in signal processing and public-key cryptography. The method combines the multiplication and division procedures by using only additions and subtractions. The full algorithm takes log2C + x steps to complete where C is the cipher text and x is a function of the number of leading zeros in C. Furthermore, due to its simplicity, the algorithm can be easily implemented using VLSI technology. Key-Words:- Multiplication, division, VLSI, signal processing, cryptography. 1.
Cited by 0
J. von Wright · 1989
A standard multiplication algorithm for square matrices is transformed into a distributed algorithm. Every transformation step is verified within the refinement calculus. Some high-level rules of refinement that are used in the derivation are proved. 1 Introduction This report is a case study, intended to show how the refinement calculus, combined with the action system formalism gives a powerful and uniform method for constructing parallel and distributed algorithms by stepwise refinement. The refinement calculus is a formalization of the stepwise refinement approach to program construction. The refinement calculus, based on the weakest precondition technique of [Dijkstra76], was first described in [Back78, Back80] and has been further elaborated in [Back87, Back88a, Back88b, MoRoGa88, Morris87]. A statement S is said to be (correctly) refined by a statement S', denoted S S 0 , if 8 P; Q:(P [S]Q ) P [S 0 ]Q) where P [S]Q stands for the total correctness of S w.r.t. precondition...
Cited by 0
Khaled Elleithy, Magdy Bayoumi · 2003
A theta (log n) algorithm for large moduli multiplication for residue-number-system (RNS)-based architectures is proposed. The 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- mu m CMOS process shows that a pipelined n-bit modulo multiplication scheme can operate with a throughput of 30M operations/s.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 1
Shang 尚 Gao 高, Yu-Guang 宇光 Yang 杨 · Chinese Physics B · 2023
Toeplitz matrix-vector multiplication is widely used in various fields, including optimal control, systolic finite field multipliers, multidimensional convolution, etc. In this paper, we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi mathvariant="script">O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>κ</mml:mi> <mml:mi mathvariant="normal">polylog</mml:mi> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> , where κ and 2 n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix, respectively. For the case with an unknown generating function, we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L 1 -norm ρ of the displacement of the structured matrices. Due to the good use of the special properties of Toeplitz matrices, the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.
Cited by 4Open access
Aleksandr Cariow, Galina Cariowa, Janusz P. Papliński · Applied Sciences · 2021
This paper presents a new algorithm for multiplying two Kaluza numbers. Performing this operation directly requires 1024 real multiplications and 992 real additions. We presented in a previous paper an effective algorithm that can compute the same result with only 512 real multiplications and 576 real additions. More effective solutions have not yet been proposed. Nevertheless, it turned out that an even more interesting solution could be found that would further reduce the computational complexity of this operation. In this article, we propose a new algorithm that allows one to calculate the product of two Kaluza numbers using only 192 multiplications and 384 additions of real numbers.
Cited by 3Open access
Dilek Öner ŞİMŞEK, Murat Cenk · 2023
In cloud computing, preserving the privacy of sensitive data poses security challenges. Homomorphic encryption offers a viable solution by enabling computations on encrypted data. Among essential operations in diverse applications, secure matrix multiplication plays a key role, particularly in statistical analysis and machine learning algorithms. While multiplying two matrices by the secure matrix multiplication, the algorithm constructs packed polynomials, encrypts them, and performs homomorphic multiplication. However, performing homomorphic multiplication on large matrices encounters difficulties due to the significant increase in the degree of packed polynomials. To enhance the efficiency of secure matrix multiplication, this paper proposes an approach that combines the Strassen algorithm and the secure matrix multiplication with the Brakerski, Gentry, and Vaikuntanathan (BGV) homomorphic encryption scheme after dividing matrices into smaller blocks. This integration offers several advantages, including reducing the number of required homomorphic encryptions from eight to seven when employing one-level recursion and better performance with smaller parameters. Our experimental results demonstrate that the Strassen method yields superior performance outcomes for large dimensions. For instance, when considering a 128 × 128 matrix and utilizing a submatrix size of two, we observe that the Strassen secure block matrix algorithm is 44% faster than the standard secure block matrix multiplication.
Cited by 1
Dharma Teja Vooturi, Kishore Kothapalli · Lecture notes in computer science · 2016
Cited by 3
Xinchun Yin · Journal of Computer Applications · 2008
Cited by 0