Concept

Basic Linear Algebra Subprograms

Related publications (19)

Randomized low-rank approximation and its applications

In this thesis we will present and analyze randomized algorithms for numerical linear algebra problems. An important theme in this thesis is randomized low-rank approximation. In particular, we will study randomized low-rank approximation of matrix functio ...

EPFL2024

TimeEvolver: A program for time evolution with improved error bound

Sebastian Zell

We present TimeEvolver, a program for computing time evolution in a generic quantum system. It relies on well-known Krylov subspace techniques to tackle the problem of multiplying the exponential of a large sparse matrix iH, where His the Hamiltonian, with ...

ELSEVIER2022

Oblivious Sketching of High-Degree Polynomial Kernels

Mikhail Kapralov, Amir Zandieh

Kernel methods are fundamental tools in machine learning that allow detection of non-linear dependencies between data without explicitly constructing feature vectors in high dimensional spaces. A major disadvantage of kernel methods is their poor scalabili ...

ASSOC COMPUTING MACHINERY2020

Fourier Sampling in Signal Processing and Numerical Linear Algebra

Amir Zandieh

This thesis focuses on developing efficient algorithmic tools for processing large datasets. In many modern data analysis tasks, the sheer volume of available datasets far outstrips our abilities to process them. This scenario commonly arises in tasks incl ...

EPFL2020

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

Stop Crying Over Your Cache Miss Rate: Handling Efficiently Thousands of Outstanding Misses in FPGAs

Paolo Ienne, Mikhail Asiatici

FPGAs rely on massive datapath parallelism to accelerate applications even with a low clock frequency. However, applications such as sparse linear algebra and graph analytics have their throughput limited by irregular accesses to external memory for which ...

ASSOC COMPUTING MACHINERY2019

Exact Smooth Term Structure Estimation

Damir Filipovic, Sander Félix M Willems

We present a non-parametric method to estimate the discount curve from market quotes based on the Moore-Penrose pseudoinverse. The discount curve reproduces the market quotes perfectly, has maximal smoothness, and is given in closed-form. The method is eas ...

2018

Exact Smooth Term-Structure Estimation

Damir Filipovic, Sander Félix M Willems

We present a nonparametric method to estimate the discount curve from market quotes based on the Moore-Penrose pseudoinverse. The discount curve reproduces the market quotes perfectly, has maximal smoothness, and is given in closed-form. The method is easy ...

SIAM PUBLICATIONS2018

Fast hierarchical solvers for symmetric eigenvalue problems

Ana Susnjara

In this thesis we address the computation of a spectral decomposition for symmetric banded matrices. In light of dealing with large-scale matrices, where classical dense linear algebra routines are not applicable, it is essential to design alternative tech ...

EPFL2018

Efficient Online Processing for Advanced Analytics

Mohamed Elsayed Mohamed Ahmed El Seidy

With the advent of emerging technologies and the Internet of Things, the importance of online data analytics has become more pronounced. Businesses and companies are adopting approaches that provide responsive analytics to stay competitive in the global ma ...

EPFL2017

Efficient Incremental Data Analysis

Milos Nikolic

Many data-intensive applications require real-time analytics over streaming data. In a growing number of domains -- sensor network monitoring, social web applications, clickstream analysis, high-frequency algorithmic trading, and fraud detections to name a ...

EPFL2016

A mixed-signal computer architecture and its application to power system problems

Theodoros Kyriakidis

Radical changes are taking place in the landscape of modern power systems. This massive shift in the way the system is designed and operated has been termed the advent of the ``smart grid''. One of its implications is a strong market pull for faster power ...

EPFL2015

Truncated low-rank methods for solving general linear matrix equations

Daniel Kressner, Petar Sirkovic

This work is concerned with the numerical solution of large-scale linear matrix equations A1XB1T++AKXBKT=C. The most straightforward approach computes XRmxn from the solution of an mn x mn linear system, typically limiting the feasible values of m,n to a f ...

Wiley-Blackwell2015

A Parallel QZ Algorithm For Distributed Memory HPC Systems

Daniel Kressner

Appearing frequently in applications, generalized eigenvalue problems represent one of the core problems in numerical linear algebra. The QZ algorithm of Moler and Stewart is the most widely used algorithm for addressing such problems. Despite its importan ...

Siam Publications2014

Optimally Packed Chains of Bulges in Multishift QR Algorithms

Daniel Kressner

The QR algorithm is the method of choice for computing all eigenvalues of a dense nonsymmetric matrix A. After an initial reduction to Hessenberg form, a QR iteration can be viewed as chasing a small bulge from the top left to the bottom right corner along ...

Association for Computing Machinery2014

LINVIEW: Incremental View Maintenance for Complex Analytical Queries

Christoph Koch, Milos Nikolic, Mohamed Elsayed Mohamed Ahmed El Seidy

Many analytics tasks and machine learning problems can be naturally expressed by iterative linear algebra programs. In this paper, we study the incremental view maintenance problem for such complex analytical queries. We develop a framework, called LINVIEW ...

2014

A Unified Framework for Max-Min and Min-Max Fairness with Applications

Jean-Yves Le Boudec

Max-min fairness is widely used in various areas of networking. In every case where it is used, there is a proof of existence and one or several algorithms for computing it; in most, but not all cases, they are based on the notion of bottlenecks. In spite ...

2007

Multimedia and food chain modelling of toxics for comparative risk and life cycle impact assessment

Ralph Rosenbaum

The overall goal of this dissertation is to contribute to the development of best available practice in environmental multimedia fate and multipathway exposure modelling for human health and ecosystem impacts, addressing several important aspects. Environm ...

EPFL2006

Variational reconstruction of scalar and vector images from non-uniform samples

Muthuvel Arigovindan

We address the problem of reconstructing scalar and vector functions from non-uniform data. The reconstruction problem is formulated as a minimization problem where the cost is a weighted sum of two terms. The first data term is the quadratic measure of go ...

EPFL2005