public inbox for gsl-discuss@sourceware.org
 help / color / mirror / Atom feed
* 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).