The Experts below are selected from a list of 12438 Experts worldwide ranked by ideXlab platform
Ornela Mulita - One of the best experts on this subject based on the ideXlab platform.
-
smoothed adaptive perturbed inverse iteration for elliptic eigenvalue problems
Computational methods in applied mathematics, 2021Co-Authors: Stefano Giani, Luka Grubisic, Luca Heltai, Ornela MulitaAbstract:We present a perturbed subspace iteration algorithm to approximate the lowermost eigenvalue cluster of an elliptic eigenvalue problem. As a prototype, we consider the Laplace eigenvalue problem posed in a polygonal domain. The algorithm is motivated by the analysis of inexact (perturbed) inverse iteration algorithms in Numerical Linear Algebra. We couple the perturbed inverse iteration approach with mesh refinement strategy based on residual estimators. We demonstrate our approach on model problems in two and three dimensions.
James Demmel - One of the best experts on this subject based on the ideXlab platform.
-
communication lower bounds and optimal algorithms for Numerical Linear Algebra
Acta Numerica, 2014Co-Authors: Grey Ballard, Erin Carson, James Demmel, Mark Hoemmen, Nicholas Knight, Oded SchwartzAbstract:The traditional metric for the efficiency of a Numerical algorithm has been the number of arithmetic operations it performs. Technological trends have long been reducing the time to perform an arithmetic operation, so it is no longer the bottleneck in many algorithms; rather, communication , or moving data, is the bottleneck. This motivates us to seek algorithms that move as little data as possible, either between levels of a memory hierarchy or between parallel processors over a network. In this paper we summarize recent progress in three aspects of this problem. First we describe lower bounds on communication. Some of these generalize known lower bounds for dense classical (O(n 3 )) matrix multiplication to all direct methods of Linear Algebra, to sequential and parallel algorithms, and to dense and sparse matrices. We also present lower bounds for Strassen-like algorithms, and for iterative methods, in particular Krylov subspace methods applied to sparse matrices. Second, we compare these lower bounds to widely used versions of these algorithms, and note that these widely used algorithms usually communicate asymptotically more than is necessary. Third, we identify or invent new algorithms for most Linear Algebra problems that do attain these lower bounds, and demonstrate large speed-ups in theory and practice.
-
accurate and efficient expression evaluation and Linear Algebra or why it can be easier to compute accurate eigenvalues of a vandermonde matrix than the accurate sum of 3 numbers
Symbolic Numeric Computation, 2012Co-Authors: James DemmelAbstract:We survey and unify recent results on the existence of accurate algorithms for evaluating multivariate polynomials, and more generally for accurate Numerical Linear Algebra with structured matrices. By "accurate" we mean the computed answer has relative error less than 1, i.e. has some leading digits correct. We also address efficiency, by which we mean algorithms that run in polynomial time in the size of the input. Our results will depend strongly on the model of arithmetic: Most of our results will use what we call the Traditional Model (TM), that the computed result of op(a, b), a binary operation like a + b, is given by op(a, b) * (1 + Δ) where all we know is that |Δ| ≤ e L 1. Here e is a constant also known as machine epsilon.
-
minimizing communication in Numerical Linear Algebra
SIAM Journal on Matrix Analysis and Applications, 2011Co-Authors: Grey Ballard, James Demmel, Olga Holtz, Oded SchwartzAbstract:In 1981 Hong and Kung proved a lower bound on the amount of communication (amount of data moved between a small, fast memory and large, slow memory) needed to perform dense, n-by-n matrix multiplication using the conventional O(n3) algorithm, where the input matrices were too large to fit in the small, fast memory. In 2004 Irony, Toledo, and Tiskin gave a new proof of this result and extended it to the parallel case (where communication means the amount of data moved between processors). In both cases the lower bound may be expressed as Ω(#arithmetic_operations/M), where M is the size of the fast memory (or local memory in the parallel case). Here we generalize these results to a much wider variety of algorithms, including LU factorization, Cholesky factorization, LDLT factorization, QR factorization, the Gram–Schmidt algorithm, and algorithms for eigenvalues and singular values, i.e., essentially all direct methods of Linear Algebra. The proof works for dense or sparse matrices and for sequential or para...
-
Numerical Linear Algebra on emerging architectures the plasma and magma projects
Journal of Physics: Conference Series, 2009Co-Authors: Emmanuel Agullo, Hatem Ltaief, Piotr Luszczek, Jack Dongarra, James Demmel, Bilel Hadri, Jakub Kurzak, Julien Langou, Stanimire TomovAbstract:The emergence and continuing use of multi-core architectures and graphics processing units require changes in the existing software and sometimes even a redesign of the established algorithms in order to take advantage of now prevailing parallelism. Parallel Linear Algebra for Scalable Multi-core Architectures (PLASMA) and Matrix Algebra on GPU and Multics Architectures (MAGMA) are two projects that aims to achieve high performance and portability across a wide range of multi-core architectures and hybrid systems respectively. We present in this document a comparative study of PLASMA's performance against established Linear Algebra packages and some preliminary results of MAGMA on hybrid multi-core and GPU systems.
-
on structure exploiting trust region regularized nonLinear least squares algorithms for neural network learning
International Joint Conference on Neural Network, 2003Co-Authors: Eiji Mizutani, James DemmelAbstract:This paper briefly introduces our Numerical Linear Algebra approaches for solving structured nonLinear least squares problems arising from 'multiple-output' neural-network (NN) models. Our algorithms feature trust-region regularization, and exploit sparsity of either the 'blockangular' residual Jacobian matrix or the 'block-arrow' Gauss-Newton Hessian (or Fisher information matrix in statistical sense) depending on problem scale so as to render a large class of NN-learning algorithms 'efficient' in both memory and operation costs. Using a relatively large real-world nonLinear regression application, we shall explain algorithmic strengths and weaknesses, analyzing simulation results obtained by both direct and iterative trust-region algorithms with two distinct NN models: 'multilayer perceptrons' (MLP) and 'complementary mixtures of MLP-experts' (or neuro-fuzzy modular networks).
Huy L Nguyen - One of the best experts on this subject based on the ideXlab platform.
-
osnap faster Numerical Linear Algebra algorithms via sparser subspace embeddings
Foundations of Computer Science, 2013Co-Authors: Jelani Nelson, Huy L NguyenAbstract:An oblivious subspace embedding (OSE) given some parameters e, d is a distribution D over matrices Π ∈ Rm×n such that for any Linear subspace W ⊆ Rn with dim(W) = d, PΠ~D(∀x ∈ W ||Πx||2 ∈ (1 ± e)||x||2) > 2/3. We show that a certain class of distributions, Oblivious Sparse Norm-Approximating Projections (OSNAPs), provides OSE's with m = O(d1+γ/e2), and where every matrix Π in the support of the OSE has only s = Oγ(1/e) non-zero entries per column, for γ > 0 any desired constant. Plugging OSNAPs into known algorithms for approximate least squares regression, lp regression, low rank approximation, and approximating leverage scores implies faster algorithms for all these problems. Our main result is essentially a Bai-Yin type theorem in random matrix theory and is likely to be of independent interest: we show that for any fixed U ∈ Rn×d with orthonormal columns and random sparse Π, all singular values of ΠU lie in [1 - e, 1 + e] with good probability. This can be seen as a generalization of the sparse Johnson-Lindenstrauss lemma, which was concerned with d = 1. Our methods also recover a slightly sharper version of a main result of [Clarkson-Woodruff, STOC 2013], with a much simpler proof. That is, we show that OSNAPs give an OSE with m = O(d2/e2), s = 1.
-
osnap faster Numerical Linear Algebra algorithms via sparser subspace embeddings
arXiv: Data Structures and Algorithms, 2012Co-Authors: Jelani Nelson, Huy L NguyenAbstract:An "oblivious subspace embedding (OSE)" given some parameters eps,d is a distribution D over matrices B in R^{m x n} such that for any Linear subspace W in R^n with dim(W) = d it holds that Pr_{B ~ D}(forall x in W ||B x||_2 in (1 +/- eps)||x||_2) > 2/3 We show an OSE exists with m = O(d^2/eps^2) and where every B in the support of D has exactly s=1 non-zero entries per column. This improves previously best known bound in [Clarkson-Woodruff, arXiv:1207.6365]. Our quadratic dependence on d is optimal for any OSE with s=1 [Nelson-Nguyen, 2012]. We also give two OSE's, which we call Oblivious Sparse Norm-Approximating Projections (OSNAPs), that both allow the parameter settings m = \~O(d/eps^2) and s = polylog(d)/eps, or m = O(d^{1+gamma}/eps^2) and s=O(1/eps) for any constant gamma>0. This m is nearly optimal since m >= d is required simply to no non-zero vector of W lands in the kernel of B. These are the first constructions with m=o(d^2) to have s=o(d). In fact, our OSNAPs are nothing more than the sparse Johnson-Lindenstrauss matrices of [Kane-Nelson, SODA 2012]. Our analyses all yield OSE's that are sampled using either O(1)-wise or O(log d)-wise independent hash functions, which provides some efficiency advantages over previous work for turnstile streaming applications. Our main result is essentially a Bai-Yin type theorem in random matrix theory and is likely to be of independent interest: i.e. we show that for any U in R^{n x d} with orthonormal columns and random sparse B, all singular values of BU lie in [1-eps, 1+eps] with good probability. Plugging OSNAPs into known algorithms for Numerical Linear Algebra problems such as approximate least squares regression, low rank approximation, and approximating leverage scores implies faster algorithms for all these problems.
Stefano Giani - One of the best experts on this subject based on the ideXlab platform.
-
smoothed adaptive perturbed inverse iteration for elliptic eigenvalue problems
Computational methods in applied mathematics, 2021Co-Authors: Stefano Giani, Luka Grubisic, Luca Heltai, Ornela MulitaAbstract:We present a perturbed subspace iteration algorithm to approximate the lowermost eigenvalue cluster of an elliptic eigenvalue problem. As a prototype, we consider the Laplace eigenvalue problem posed in a polygonal domain. The algorithm is motivated by the analysis of inexact (perturbed) inverse iteration algorithms in Numerical Linear Algebra. We couple the perturbed inverse iteration approach with mesh refinement strategy based on residual estimators. We demonstrate our approach on model problems in two and three dimensions.
Woodruff, David P. - One of the best experts on this subject based on the ideXlab platform.
-
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
2021Co-Authors: Chepurko Nadiia, Clarkson, Kenneth L., Horesh Lior, Lin Honghao, Woodruff, David P.Abstract:We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De-quantizing such algorithms has received a flurry of attention in recent years; we obtain sharper bounds for these problems. More significantly, we achieve these improvements by arguing that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise; these are powerful and standard techniques in randomized Numerical Linear Algebra. With this recognition, we are able to employ the large body of work in Numerical Linear Algebra to obtain algorithms for these problems that are simpler or faster (or both) than existing approaches.Comment: Adding new Numerical experiment
-
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
2020Co-Authors: Chepurko Nadiia, Clarkson, Kenneth L., Horesh Lior, Woodruff, David P.Abstract:We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De-quantizing such algorithms has received a flurry of attention in recent years; we obtain sharper bounds for these problems. More significantly, we achieve these improvements by arguing that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise. With this recognition, we are able to employ the large body of work in Numerical Linear Algebra to obtain algorithms for these problems that are simpler and faster than existing approaches. We also consider static data structures for the above problems, and obtain close-to-optimal bounds for them. To do this, we introduce a new randomized transform, the Gaussian Randomized Hadamard Transform (GRHT). It was thought in the Numerical Linear Algebra community that to obtain nearly-optimal bounds for various problems such as rank computation, finding a maximal Linearly independent subset of columns, regression, low rank approximation, maximum matching on general graphs and Linear matroid union, that one would need to resolve the main open question of Nelson and Nguyen (FOCS, 2013) regarding the logarithmic factors in existing oblivious subspace embeddings. We bypass this question, using GRHT, and obtain optimal or nearly-optimal bounds for these problems. For the fundamental problems of rank computation and finding a Linearly independent subset of columns, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013) and are optimal to within a constant factor and a $\log\log(n)$-factor, respectively. Further, for constant factor regression and low rank approximation we give the first optimal algorithms, for the current matrix multiplication exponent.Comment: Adding acknowledgements and updating comparison to concurrent wor
-
SubLinear Time Numerical Linear Algebra for Structured Matrices
2019Co-Authors: Shi Xiaofei, Woodruff, David P.Abstract:We show how to solve a number of problems in Numerical Linear Algebra, such as least squares regression, $\ell_p$-regression for any $p \geq 1$, low rank approximation, and kernel regression, in time $T(A) \poly(\log(nd))$, where for a given input matrix $A \in \mathbb{R}^{n \times d}$, $T(A)$ is the time needed to compute $A\cdot y$ for an arbitrary vector $y \in \mathbb{R}^d$. Since $T(A) \leq O(\nnz(A))$, where $\nnz(A)$ denotes the number of non-zero entries of $A$, the time is no worse, up to polylogarithmic factors, as all of the recent advances for such problems that run in input-sparsity time. However, for many applications, $T(A)$ can be much smaller than $\nnz(A)$, yielding significantly subLinear time algorithms. For example, in the overconstrained $(1+\epsilon)$-approximate polynomial interpolation problem, $A$ is a Vandermonde matrix and $T(A) = O(n \log n)$; in this case our running time is $n \cdot \poly(\log n) + \poly(d/\epsilon)$ and we recover the results of \cite{avron2013sketching} as a special case. For overconstrained autoregression, which is a common problem arising in dynamical systems, $T(A) = O(n \log n)$, and we immediately obtain $n \cdot \poly(\log n) + \poly(d/\epsilon)$ time. For kernel autoregression, we significantly improve the running time of prior algorithms for general kernels. For the important case of autoregression with the polynomial kernel and arbitrary target vector $b\in\mathbb{R}^n$, we obtain even faster algorithms. Our algorithms show that, perhaps surprisingly, most of these optimization problems do not require much more time than that of a polylogarithmic number of matrix-vector multiplications
