Randomised Methods for Computing the QR Decomposition of a Tall-Skinny Matrix
(2025) In Bachelor's Theses in Mathematical Sciences NUMK11 20251Centre for Mathematical Sciences
Mathematics (Faculty of Sciences)
- Abstract
- The QR decomposition is used to solve least squares problems, systems of equations and other important linear algebra tasks. We consider the computation of the QR decomposition for tall-skinny matrices, using the Cholesky decomposition as an intermediate step. To improve efficiency, we introduce randomised numerical linear algebra and sketching as a tool for improving computational efficiency. Numerical experiments are performed comparing the accuracy and runtime of randomised algorithms to classical methods and built-in functions from NumPy and SciPy. They demonstrate that, when applicable, the randomised methods return accurate results in less time than all alternatives.
- Popular Abstract
- Companies and researchers collect more data than ever. This collected data is usually stored as a large table of numbers called a matrix.
In many cases, matrices possess billions of measurements for hundreds of different, possibly related things. Since we have a lot more rows of data than things to measure, this table of numbers looks very tall and thin, so we call it a tall-skinny matrix.
Just like 12 can be split into 3 × 4 or 2 × 6, matrices can be decomposed into parts. There are different ways to split up a number; similarly, there are many ways to decompose a matrix.
One useful option is called the QR decomposition, as it helps to uncover relationships between the different things being measured.
When decomposing a... (More) - Companies and researchers collect more data than ever. This collected data is usually stored as a large table of numbers called a matrix.
In many cases, matrices possess billions of measurements for hundreds of different, possibly related things. Since we have a lot more rows of data than things to measure, this table of numbers looks very tall and thin, so we call it a tall-skinny matrix.
Just like 12 can be split into 3 × 4 or 2 × 6, matrices can be decomposed into parts. There are different ways to split up a number; similarly, there are many ways to decompose a matrix.
One useful option is called the QR decomposition, as it helps to uncover relationships between the different things being measured.
When decomposing a huge matrix, though, efficiency is crucial, since a weak computer or a slow method would fail to produce results in any reasonable amount of time. We need large and powerful computers to tackle such a problem, and we need methods that can make full use of all the available power.
In the last couple of decades, there have been several discoveries of faster ways to decompose matrices, and one such discovery is that of randomised methods. They involve, for example, randomly selecting a few hundred rows of the matrix, and doing some of the steps using this smaller matrix instead of the huge original one.
Conveniently, the results remain very accurate, because the smaller matrix typically retains many of the characteristics of the original matrix.
We compare some randomised methods to traditional ways of computing the QR decomposition. The methods are written in the Python programming language, also using two additional tools called NumPy and SciPy. Through different tests, we measure the accuracy of the results and the time in which they are computed.
Our findings are that the randomised methods are the fastest way to get consistently accurate results in most cases, but to unlock their potential on powerful computers, these methods would benefit from being implemented with tools that target such systems, possibly outside of Python. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9200396
- author
- Vijups, Artis LU
- supervisor
- organization
- course
- NUMK11 20251
- year
- 2025
- type
- M2 - Bachelor Degree
- subject
- keywords
- Numerical Analysis, Numerical Linear Algebra, Randomization, Matrix Factorization, QR Decomposition, Cholesky Decomposition, Scalability
- publication/series
- Bachelor's Theses in Mathematical Sciences
- report number
- LUNFNA-4066-2025
- ISSN
- 1654-6229
- other publication id
- 2025:K22
- language
- English
- id
- 9200396
- date added to LUP
- 2025-09-01 13:52:44
- date last changed
- 2025-09-01 13:52:44
@misc{9200396,
abstract = {{The QR decomposition is used to solve least squares problems, systems of equations and other important linear algebra tasks. We consider the computation of the QR decomposition for tall-skinny matrices, using the Cholesky decomposition as an intermediate step. To improve efficiency, we introduce randomised numerical linear algebra and sketching as a tool for improving computational efficiency. Numerical experiments are performed comparing the accuracy and runtime of randomised algorithms to classical methods and built-in functions from NumPy and SciPy. They demonstrate that, when applicable, the randomised methods return accurate results in less time than all alternatives.}},
author = {{Vijups, Artis}},
issn = {{1654-6229}},
language = {{eng}},
note = {{Student Paper}},
series = {{Bachelor's Theses in Mathematical Sciences}},
title = {{Randomised Methods for Computing the QR Decomposition of a Tall-Skinny Matrix}},
year = {{2025}},
}