In his book "Algorithmic Trading", E.P. Chan discusses some trading ideas based upon mean reversion and momentum trading styles. As part of the algorithm discussions, he refers to some statistical tests. One of the statistical tests is the Augmented Dickey Fuller Test.
That test seems easy to acquire if one is using Python, R, or many other languages. It just isn't readily available in C++. For those heavy into statistics, it is said to be easy to implement. I was hoping not to spend too much time on the implementation, so sought out some sources. The Wikipedia Entry.
One application package, Stata, has description of their dfuller test. The test statistic from this C++ library matches the Stata library based statistic when using the Box, Jenkins, and Reinsel (2008) Series G data set.
Searching didn't result in much, other than a link to a Wilmott Forum entry called
VBA code to perform the Augmented Dickey Fuller? There are some links to a Korean language blog. By running Google Translate on the pages, some useful information becomes available.
The source for a functioning
Augmented Dickey Fuller Unit Root Test is found in the blog. The Source refers to a third party matrix operations library called 'newmat', the source of which can be found at Newmat C++ Matrix Library. There are two versions, a v10, and a v11. The ADF code references v10, but I downloaded v11, and was able to link, build and run successfully.
There is a link to a VBA Code and Spreadsheet. The VBA code references the C++ library. But more importantly, the spreadsheet has the test values for verifying the code works. In the code, embedded are results for two lag tests, one with a value of 0, and one with a value of 3. The project matches the tests provided from the original web site.
I have assembled the NewMat library, the ADF subroutine, and the test data into a
Microsoft Visual C++ 2012 Project File.
Since NewMat doesn't look to have many recent revisions, it might be wise to convert the matrix operations to maybe uBLAS from the Boost libraries.
To convert the code directly requires matrix inversion. As Boost based uBLAS doesn't offer such a function, an inversion function would have to be conjured up. Fortunately, someone else has created such an animal at
C++ matrix inversion (boost::ublas). Here is the original source for the LU Matrix Inversion subroutine.
From the Boost Users List, a few suggestions are provided:
- at the beginning, check that the matrix is square
- in the case of a singular matrix, return a matrix with all values set to infinity
- check if the inverse matrix is different, and if so, resize to match the input matrix
- as a side issue, "matrix inverse to solve a linear system is probably the worst way to solve it", "high
performance linear algebra where inversion is a no no"
- side comment: "LU is a factorization of the matrix not a inverse...in real life
inverting the matrix is only for small examples"
- insight: "A triangular matrix has zero elements below the diagonal (upper triangular)
or above the diagonal (lower triangular). This way a nonsingular triangular
matrix can be inverted in straightforward manner. LU decomposition allows to
produce two triangular matrices which product is your source matrix. A
matrix inversion can be implemented by means of these succeeding operations"
- comment: "LU is a good method for Matrix Inverse (see Numerical Recipes). Been using it for quite a while. You can always calculate the determinant of the inverse and multiply it with the determinant of the original Matrix to determine how good the inversion is"
- comment: "For Kalman filters, ensure that the matrices are stable ie Determinants are not near zero"
- warning: "be aware of floating point limitations on your system, it will impact the max Matrix size and its stability criterion"
When using the Boost uBLAS matrix library, there are some helpful hints at
Effective uBLAS. A couple of hints include: a) some typedefs for common matrix types, eg 'ublas::bounded_vector<double, 3>', and b) getting vectors to display cleanly in the Microsoft Visual Studio debugger.
Continue reading "C++ Augmented Dickey Fuller Test (ADF)" »