From: Patrick Alken <alken@colorado.edu>
To: "gsl-discuss@sourceware.org" <gsl-discuss@sourceware.org>
Subject: Large linear least squares
Date: Mon, 09 Nov 2015 22:16:00 -0000 [thread overview]
Message-ID: <56411B37.2050504@colorado.edu> (raw)
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
reply other threads:[~2015-11-09 22:16 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=56411B37.2050504@colorado.edu \
--to=alken@colorado.edu \
--cc=gsl-discuss@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).