Matrix multiplication algorithm

Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network). Directly applying the mathematical definition of matrix multiplication gives an algorithm that takes time on the order of n3 field operations to multiply two n × n matrices over that field (Θ(n3) in big O notation). Better asymptotic bounds on the time required to multiply matrices have been known since the Strassen's algorithm in the 1960s, but

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (8)

Related publications

Related people

Related units

Related concepts (9)

Related concepts

Related courses (16)

Related courses

Related lectures (21)

Related lectures

Strassen algorithm

In linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication. It is faster than the standard matrix multiplication algorithm for large matrices,

Divide-and-conquer algorithm

In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, un

Basic Linear Algebra Subprograms

Basic Linear Algebra Subprograms (BLAS) is a specification that prescribes a set of low-level routines for performing common linear algebra operations such as vector addition, scalar multiplication, d

Scalable parallelization of skyline computation for multi-core processors

Darius Sidlauskas

The skyline is an important query operator for multi-criteria decision making. It reduces a dataset to only those points that offer optimal trade-offs of dimensions. In general, it is very expensive to compute. Recently, multicore CPU algorithms have been proposed to accelerate the computation of the skyline. However, they do not sufficiently minimize dominance tests and so are not competitive with state-of-the-art sequential algorithms. In this paper, we introduce a novel multicore skyline algorithm, Hybrid, which processes points in blocks. It maintains a shared, global skyline among all threads, which is used to minimize dominance tests while maintaining high throughput. The algorithm uses an efficiently-updatable data structure over the shared, global skyline, based on point-based partitioning. Also, we release a large benchmark of optimized skyline algorithms, with which we demonstrate on challenging workloads a 100-fold speedup over state-of-the-art multicore algorithms and a 10-fold speedup with 16 cores over state-of-the-art sequential algorithms.

IEEE2015

Masking vs. Multiparty Computation: How Large Is the Gap for AES?

Sebastian Faust

In this paper, we evaluate the performances of state-of-the art higher-order masking schemes for the AES. Doing so, we pay a particular attention to the comparison between specialized solutions introduced exclusively as countermeasures against side-channel analysis, and a recent proposal by Roche and Prouff exploiting MultiParty Computation (MPC) techniques. We show that the additional security features this latter scheme provides (e.g. its glitch-freeness) comes at the cost of large performance overheads.We then study how exploiting standard optimization techniques from the MPC literature can be used to reduce this gap. In particular, we show that “packed secret sharing” based on a modified multiplication algorithm can speed up MPC-based masking when the order of the masking scheme increases. Eventually, we discuss the randomness requirements of masked implementations. For this purpose, we first show with information theoretic arguments that the security guarantees of masking are only preserved if this randomness is uniform, and analyze the consequences of a deviation from this requirement. We then conclude the paper by including the cost of randomness generation in our performance evaluations. These results should help actual designers to choose a masking scheme based on security and performance constraints.

2013

On finitely generated modules over quasi-Euclidean rings

Luc Guyot

Let R be a unital commutative ring, and let M be an R-module that is generated by k elements but not less. Let be the subgroup of generated by the elementary matrices. In this paper we study the action of by matrix multiplication on the set of unimodular rows of M of length . Assuming R is moreover Noetherian and quasi-Euclidean, e.g., R is a direct product of finitely many Euclidean rings, we show that this action is transitive if . We also prove that is equipotent with the unit group of where is the first invariant factor of M. These results encompass the well-known classification of Nielsen non-equivalent generating tuples in finitely generated Abelian groups.

Springer Verlag2017

CS-431: Introduction to natural language processing

The objective of this course is to present the main models, formalisms and algorithms necessary for the development of applications in the field of natural language information processing. The concepts introduced during the lectures will be applied during practical sessions.

PHYS-332: Computational physics III

This course teaches the students practical skills needed for solving modern physics problems by means of computation. A number of examples illustrate the utility of numerical computations in various domains of physics.

MATH-111(en): Linear algebra (english)

The purpose of the course is to introduce the basic notions of linear algebra and its applications.