Sunday, April 21, 2013

Dual basis and its applications

In the physical sciences, the scientist mostly tries to put the problem in a form that is easily solvable. One such form is the eigenvector expansion where one solves a simpler problem and assumes that the more difficult problem can be decomposed in a sum of the simpler solutions.
This kind of problem generally involves solving the eigenvalue problem of a particular matrix. Assuming that you know how to do that, this is all fine and well. However, it is also common to use orthogonality relations to simplify the solution. For a general matrix $A$, the resulting eigenvectors need not be orthogonal. That's a problem. Let's look for a solution.
Adopting the braket notation and denoting an eigenvector by $|e_i\rangle$, we seek new vectors such that $$\langle f^i|e_j\rangle = \delta^i_j.$$ To see how we can compute those vectors, consider the original eigenvalue problem $$\label{eq:eigenvalue}A|e_i\rangle = \lambda_i|e_i\rangle .$$ We will use the fact that both sets of eigenvectors are complete so that there exists a closure relation $$\sum_i |e_i\rangle\langle f^i| = 1.$$ Now, pre-multipling \eqref{eq:eigenvalue} by $\langle f^j|$ and post-multiplying by $\langle f^i|$ and summing over the index $i$, we get $$\sum_i \langle f^j|A|e_i\rangle\langle f^i| = \sum_i \lambda_i \langle f^j|e_i\rangle\langle f^i|.$$ Using our orthogonality relations on the right-hand side of this last equation and the closure relation on the left-hand side, we get $$\langle f^j| A = \sum_i \lambda_i \langle f^i| \delta^j_i.$$ The Dirac delta makes the sum disappear as usual and we have $$\langle f^j| A = \lambda_j \langle f^j|.$$ In other words, the $\langle f^j|$ are the row eigenvectors of $A$ and have the same eigenvalues as the set $|e_i\rangle$!
So we find that these new "contravariant" vectors are actually the left eigenvectors of the matrix $A$. Moreover, the decomposition of any vector in the original set of covariant vectors is given by the dot product with the vectors in the dual basis. Say we have a vector $|v\rangle$, its decomposition is given by $$|v\rangle = \sum_i \langle f^i|v\rangle|e_i\rangle .$$
This eigendecomposition is incredibly useful in solving differential equations, smoothing numerically unstable solutions...

Sunday, March 10, 2013

Interfacing Armadillo and FFTW

FFTW, or the Fastest Fourier Transform in the West, is an awesome C library used to, well, perform FFTs. Armadillo, on the other hand, is an awesome C++ library that implements linear algebra operations. Both are renowned for their amazing speed and, especially the latter, ease of use.
Now suppose you want to use Armadillo in concert with FFTW. By default, FFTW assumes that you are using fftw_complex* arrays which memory are allocated using fftw_malloc. Now, assuming that you want to transform elements of an Armadillo vector or matrix, copying the data from the matrix to a newly allocated array may not be desirable (or it might be, depending on the performance hit incurred by not using fftw_malloc). Then, your C++ code should be something like
I'm by no means an expert, but this snippet works beautifully in my own code.
Please feel free to point out any factual errors.
Update: Note that the operations in the Gist do not commute, i.e. the order in which they are done is important. If you put data in the samples matrix before creating the plan, your columns will be overwritten. Pay attention!

Thursday, January 24, 2013

Arrow in the Knee: the Genesis

So my wife was re-reading the epic fantasy pentalogy The Belgariad by David Eddings [1]. It's a fantastic coming-of-age, prophecy-fulfilling, magic-filled story. Every character is fully developed and they are all thoroughly likable.

But now to the important part. In the Queen of Sorcery book [2,p.222], originally published in 1982, it is revealed that Count Reldegen, an Asturian, is limping. This sparks the following conversation:
"What happened to your leg?" Wolf asked him.
"An arrow in the knee." The count shrugged.
Yes, that's right, an arrow in the knee!

Now go read The Belgariad so you know why it matters that Reldegen is an Asturian.

[1] Amateurish introductory line, I know.
[2] D. Eddings. Queen of Sorcery in The Belgariad. 2002. New York: Ballantine.