* **Large linear least squares**
**@ 2015-11-09 22:16 Patrick Alken**
0 siblings, 0 replies; only message in thread
From: Patrick Alken @ 2015-11-09 22:16 UTC (permalink / raw)
To: gsl-discuss
Hello all,
I have implemented two solvers for large linear least squares systems
in GSL. These routines are designed for so called "Tall Skinny"
matrices, which have many more rows than columns. The main idea is to
accumulate the matrix one block of rows at a time to avoid having to
store the entire matrix in memory at once (which may not be possible
depending on the size of your matrix).
The first method is the normal equations method, which is well known
and popular for its speed and simplicity. This method calculates and
stores only the normal equations matrix X^T X which is much smaller than
the full matrix X. The normal equations method is accurate when applied
to well conditioned matrices, but suffers from numerical instabilities
for ill-conditioned matrices.
The second method is the Tall Skinny QR (TSQR) algorithm from Demmel
et al, 2008. This method calculates the QR decomposition of X, updating
the R factor each time a new block of rows is added to the system. Since
its based on a QR decomposition, it is much more stable than the normal
equations method on badly conditioned matrices, though the method is
roughly twice as slow as the normal equations for n >> m.
Everything is on the git and documented, with an example program.
Feedback is always welcome. I am planning to push out a 2.1 release soon
due to a few of the bugs reported over the last couple weeks.
Thanks,
Patrick
^ permalink raw reply [**flat**|nested] only message in thread

only message in thread, other threads:[~2015-11-09 22:16 UTC | newest]
**Thread overview:** (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-11-09 22:16 Large linear least squares Patrick Alken

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).