Wednesday, 17 June 2009

Least squares: a case study in optimization

The F#.NET Journal just published an article about curve fitting:

"The challenge of finding the least squares best fit of a linear sum of functions is a common problem in regression. Linear algebra provides a powerful and general solution by expressing this problem in terms of matrices and then computing the QR decomposition in order to solve the matrix equation. This article describes a remarkably simple implementation of QR decomposition in F# before developing progressively more optimized implementations using the guidance of performance profiles and without sacrificing generality. In particular, heavy use of the F# keyword "inline" is made in order to express efficient reusable numerical methods..."

To read this article and more, subscribe to The F#.NET Journal today!


Art said...

Hi Jon.
Whilst reading Golub and Van Loan Matrix Computations, Thrid Edition, ... 8.4.6 Parallel Jacobi, pg. 431, "... Perhaps the most interesting distinction between the QR and the Jacobi approaches to the symmetric eigenvalue problem is the rich inherent parallelism of the latter. ... rotations within each ... "non-conflicting." ... a parallel ordering of the set ... .

Question -- what is the performance difference? And will many-core architectures capture the benefit? CPU? or GPU?

Jon Harrop said...

@Art: Good question. I don't know what the performance difference between QR and Jacobi is but this article covered QR and the article Visualizing linear algebra: Singular Value Decomposition used Jacobi. I'll benchmark them when I get the chance.