Publications related to Computational complexity of matrix multiplication

COMMUNICATION LOWER BOUNDS AND OPTIMAL ALGORITHMS FOR MULTIPLE TENSOR-TIMES-MATRIX COMPUTATION

Multiple tensor-times-matrix (Multi-TTM) is a key computation in algorithms for computing and operating with the Tucker tensor decomposition, which is frequently used in multidimensional data analysis. We establish communication lower bounds that determine ...

Siam Publications2024

A 16-bit Floating-Point Near-SRAM Architecture for Low-power Sparse Matrix-Vector Multiplication

David Atienza Alonso, Giovanni Ansaloni, Grégoire Axel Eggermann, Marco Antonio Rios

State-of-the-art Artificial Intelligence (AI) algorithms, such as graph neural networks and recommendation systems, require floating-point computation of very large matrix multiplications over sparse data. Their execution in resource-constrained scenarios, ...

New York2023

Preconditioning techniques for generalized Sylvester matrix equations

Yannis Dirk Voet

Sylvester matrix equations are ubiquitous in scientific computing. However, few solution techniques exist for their generalized multiterm version, as they now arise in an increasingly large number of applications. In this work, we consider algebraic parame ...

2023

Post-Moore's Law Fusion: High-Bandwidth Memory, Accelerators, and Native Half-Precision Processing for CPU-Local Analytics

Anastasia Ailamaki, Viktor Sanca

Modern data management systems aim to provide both cutting-edge functionality and hardware efficiency. With the advent of AI-driven data processing and the post-Moore Law era, traditional memory-bound scale-up data management operations face scalability ch ...

2023

How to Achieve Large-Area Ultra-Fast Operation of MoS 2 Monolayer Flash Memories?

Aleksandra Radenovic, Andras Kis, Mukesh Kumar Tripathi, Asmund Kjellegaard Ottesen, Yanfei Zhao, Guilherme Migliato Marega, Zhenyu Wang, Hyungoo Ji

Memory devices have returned to the spotlight due to increasing interest in using in-memory computing architectures to make data-driven algorithms more energy-efficient. One of the main advantages of this architecture is the efficient performance of vector ...

2023

Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

Alice Cortinovis

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices. In the first part, we consider algorithms for building ...

EPFL2022

Fabrication and Characterization of High Aspect Ratio Amorphous Silicon Based Microchannel Plates

Christophe Ballif, Nicolas Würsch, Janina Christine Isabelle Löffler, Samira Alexandra Frey, Mohammad Beygi

This contribution focuses on the fabrication and characterization of microchannel plates made of hydrogenated amorphous silicon (AMCPs). Flexible fabrication processes and the semi-conducting nature of amorphous silicon could give these detectors the advan ...

2021

Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)

Rachid Guerraoui, Sadegh Farhadkhani, El Mahdi El Mhamdi, Le Nguyen Hoang, Sébastien Louis Alexandre Rouault, Arsany Hany Abdelmessih Guirguis

We study Byzantine collaborative learning, where n nodes seek to collectively learn from each others' local data. The data distribution may vary from one node to another. No node is trusted, and f < n nodes can behave arbitrarily. We prove that collaborati ...

2021

ESSOP: Efficient and Scalable Stochastic Outer Product Architecture for Deep Learning

Irem Boybat Kara, Evangelos Eleftheriou, Abu Sebastian

Deep neural networks (DNNs) have surpassed human-level accuracy in a variety of cognitive tasks but at the cost of significant memory/time requirements in DNN training. This limits their deployment in energy and memory limited applications that require rea ...

IEEE2020

A Logic Synthesis Toolbox for Reducing the Multiplicative Complexity in Logic Networks

Giovanni De Micheli, Mathias Soeken, Luca Gaetano Amarù, Eleonora Testa, Heinz Riener

Logic synthesis is a fundamental step in the realization of modern integrated circuits. It has traditionally been employed for the optimization of CMOS-based designs, as well as for emerging technologies and quantum computing. Recently, it found applicatio ...

IEEE2020

Non-filamentary non-volatile memory elements as synapses in neuromorphic systems

Yusuf Leblebici, Alessandro Fumarola, Severin Sidler

Crossbar arrays of non-volatile memory (NVM) devices represent one possible path for implementing highly energy-efficient neuromorphic computing systems. For Deep Neural Networks (DNN), where information can be encoded as analog voltage and current levels, ...

IEEE2019

Backpropagation-Friendly Eigendecomposition

Pascal Fua, Mathieu Salzmann, Zheng Dang, Wei Wang, Yinlin Hu

Eigendecomposition (ED) is widely used in deep networks. However, the backpropagation of its results tends to be numerically unstable, whether using ED directly or approximating it with the Power Iteration method, particularly when dealing with large matri ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2019

Characterization of Amorphous Silicon Based Microchannel Plates with High Aspect Ratio

Christophe Ballif, Nicolas Würsch, Janina Christine Isabelle Löffler, Samira Alexandra Frey

Microchannel plates (MCPs) fabricated out of hydrogenated amorphous silicon offer a promising alternative to conventional lead glass ones. Progress in the fabrication process has allowed for detectors with higher aspect ratios, which significantly increase ...

IEEE2019

Reducing the Multiplicative Complexity in Logic Networks for Cryptography and Security Applications

Giovanni De Micheli, Mathias Soeken, Luca Gaetano Amarù, Eleonora Testa

Reducing the number of AND gates plays a central role in many cryptography and security applications. We propose a logic synthesis algorithm and tool to minimize the number of AND gates in a logic network composed of AND, XOR, and inverter gates. Our appro ...

ASSOC COMPUTING MACHINERY2019

The Role of Multiplicative Complexity in Compiling Low T-count Oracle Circuits

Giovanni De Micheli, Mathias Soeken, Giulia Meuli

We present a constructive method to create quantum circuits that implement oracles vertical bar x vertical bar y |0 (k) -> vertical bar x vertical bar y circle plus f(x)vertical bar 0 (k) for n-variable Boolean functions f with low T-count. In our method f ...

IEEE2019

Increasing Availability in Distributed Storage Systems via Clustering

Michael Christoph Gastpar, Saeid Sahraei

We introduce the Fixed Cluster Repair System (FCRS) as a novel architecture for Distributed Storage Systems (DSS) that achieves a small repair bandwidth while guaranteeing a high availability. Specifically, we partition the set of servers in a DSS into s c ...

2018

Learning of robust spectral graph dictionaries for distributed processing

Pascal Frossard, Ntorina Thanou

We consider the problem of distributed representation of signals in sensor networks, where sensors exchange quantized information with their neighbors. The signals of interest are assumed to have a sparse representation with spectral graph dictionaries. We ...

SPRINGEROPEN2018

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 r ...

Springer Verlag2017

On the Continuous Steering of the Scale of Tight Wavelet Frames

Michaël Unser, Daniel Sage, Zsuzsanna Püspöki, John Paul Ward

In analogy with steerable wavelets, we present a general construction of adaptable tight wavelet frames, with an emphasis on scaling operations. In particular, the derived wavelets can be "dilated" by a procedure comparable to the operation of steering ste ...

SIAM2016

Computational Aspects of Jacobians of Hyperelliptic Curves

Alina Dudeanu

Nowadays, one area of research in cryptanalysis is solving the Discrete Logarithm Problem (DLP) in finite groups whose group representation is not yet exploited. For such groups, the best one can do is using a generic method to attack the DLP, the fastest ...

EPFL2016