StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You need the solution to an overdetermined linear system. The popular methods are Normal Equations (not usually recommended), QR factorization, and singular value decomposition (SVD). Wikipedia has decent explanations, <a href="http://www.comlab.ox.ac.uk/nick.trefethen/text.html" rel="nofollow noreferrer">Trefethen and Bau</a> is very good. Your options:</p> <ol> <li><p>Out-of-core implementation via the normal equations. This requires the product <code>A'A</code> where <code>A</code> has many more rows than columns (so the result is very small). The matrix <code>A</code> is completely defined by the sample locations so you don't have to store it, thus computing <code>A'A</code> is reasonably cheap (very cheap if you don't need to hit memory for the node locations). Once <code>A'A</code> is computed, you get the solution in one pass through your input data, but the method can be unstable.</p></li> <li><p>Implement an out-of-core QR factorization. Classical Gram-Schmidt will be fastest, but you have to be careful about stability.</p></li> <li><p>Do it in-core with distributed memory (if you have the hardware available). Libraries like PLAPACK and SCALAPACK can do this, the performance should be much better than 1. The parallel scalability is not fantastic, but will be fine if it's a problem size that you would even think about doing in serial.</p></li> <li><p>Use iterative methods to compute an SVD. Depending on the spectral properties of your system (maybe after preconditioning) this could converge very fast and does not require storage for the matrix (which in your case has 5-10 columns each of which are the size of your input data. A good library for this is <a href="http://www.grycap.upv.es/slepc/" rel="nofollow noreferrer">SLEPc</a>, you only have to find a the product of the Vandermonde matrix with a vector (so you only need to store the sample locations). This is very scalable in parallel.</p></li> </ol>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload