Financial time series and Q

   "Know how to solve every problem that has been solved"

                                                                                       - Richard Feynman

Q, the sequel to K, is a proprietry language specialised for array processing and time series analytics. It provides a query language via KDB+, an in-memory column-based database. Q has it's roots as a variant of APL providing very terse and powerful langauge constructs that is able to solve complex algorithmic problems using extremely short lines of code. This page is devoted to showcasing misc. stuff related to Q/K.

Q and GPU processing using CUDA

Having my roots as a graphics junkie, I of course had to bring the recent craze in GPU computation to time-series analytics ;) The below example shows CUDA super charging Q for a greater than 6x performance boost in a simple vwap computation.

cuda

Data parallel algorithms enabled thru the use of CUDA certainly finds a perfect application in financial time series, from the simple case of vwap to black scholes, monte carlo option pricing. It certainly excites me alot that I'll be able to bring my graphics expertise to the world of fiannce. More stuff will be posted later on various data parallel implementations of quantitative analytics.

Computational Geometry and Bitemporal Databases

Another interesting discovery with my foray into the world of finance is the link between the concept of bi-temporal databases and rectangular subdivisions in computation geometry. The image below shows an actual information visualization of a working Q bitemporal database. This immediately opens up the possibility of accelerating search using point location in rectangular subdivisions (see info here).

LU decomposition

m:(25.0 5.0 1.0; 64.0 8.0 1.0; 144.0 12.0 1.0)
// process diagonal element x
p:{ indices:(x+1) _ til count m;
m[indices;x]:m[indices;x]%m[x;x];
idx :: raze indices ,/:\: indices;
g:e[;x];g each idx;}

e:{ i:x[0]; j:x[1];
m[i;j]:m[i;j]-(m[i;y]*m[y;j]);
}

// code
show m
p each til ((count m)-1)

m contains the LU decomposition in place.

Solving P326 Extrapolation Using Table in Q

q)k:1
q)a:3 6 10 15
q)last last sums\[k;reverse last each {1_deltas x}\ [a]]
21

q)k:2
q)a:3 6 10 15
q)last last sums\[k;reverse last each {1_deltas x}\ [a]]
28

q)k:20
q)a:2 4 6
q)last last sums\[k;reverse last each {1_deltas x}\ [a]]
46

q)k:10
q)a:3 9 12 5 18 -4
q)last last sums\[k;reverse last each {1_deltas x}\ [a]]
-319268

 

Computing Matrix Trace in Q

m:(-1 2 3;4 5 6;7 8 9)
sum m @' til 3

13

Gaussian Random Number Generation in Q via the Box-Muller transform

 

 

bm:{ r : last {p: -1 + (2?2.0); xx::p 0; sum p*p}\[1<;2];
        :xx * sqrt ((-2.0 * log r) % r) }
list : bm\[500000;0]    


randomwalk : sums bm\[500000;0] 

The above shows the implementation of gaussian normal random variable using the Box-Muller transform and a realization of a random walk in Q.
The histogram generation is easily achieved using the Q code below.

Q source code 

Output 

mb:{[x;y;step] v:(`int$(y-x)%step); : raze (`float$x), x +\ (v, 1) # step }

grp:{[values;rx;ry;step] group mb[rx;ry;step] bin values}

hist:{[values;rx;ry;step]
 c: `int$(1+(ry-rx)%step);
 d: grp[values;rx;ry;step];
 e: ((til c)! (c,1)# 0);
 mb[rx;ry;step] ! value raze each e , count each d
 }

rl : 1 _ bm\[5000;0]
hist[rl;-5.0;5;0.3] 

 -5  | 0
-4.7| 0
-4.4| 0
-4.1| 0
-3.8| 0
-3.5| 2
-3.2| 5
-2.9| 7
-2.6| 26
-2.3| 62
-2  | 123
-1.7| 187
-1.4| 259
-1.1| 364
-0.8| 481
-0.5| 522
-0.2| 633
0.1 | 601
0.4 | 531
0.7 | 400
1   | 340
1.3 | 222
1.6 | 101
1.9 | 65
2.2 | 37
2.5 | 16
2.8 | 13
3.1 | 3
3.4 | 0
3.7 | 0
4   | 0
4.3 | 0
4.6 | 0
4.9 | 0

Sliding window over a list of values

The sliding window function provides a sliding window of size x over a list y 

q)sw:{{1 _ x, y}\[x # 0; y]}
q)z
3.927524 5.170911 5.159796 4.066642 1.780839 3.017723 7.85033 5.347096 7.111716 4.11597
q)sw[1;z]
3.927524
5.170911
5.159796
4.066642
1.780839
3.017723
7.85033
5.347096
7.111716
4.11597
q)sw[2;z]
0        3.927524
3.927524 5.170911
5.170911 5.159796
5.159796 4.066642
4.066642 1.780839
1.780839 3.017723
3.017723 7.85033
7.85033  5.347096
5.347096 7.111716
7.111716 4.11597
q)sw[3;z]
0        0        3.927524
0        3.927524 5.170911
3.927524 5.170911 5.159796
5.170911 5.159796 4.066642
5.159796 4.066642 1.780839
4.066642 1.780839 3.017723
1.780839 3.017723 7.85033
3.017723 7.85033  5.347096
7.85033  5.347096 7.111716
5.347096 7.111716 4.11597

Autoregressive Process

An autoregressive process of order p, AR(p) is given by

Xt = a + c1Xt-1 + c2Xt-2 + ... + cpXt-p + Wt

where a is a constant term and Wt is white noise. The following Q code generates a AR(p) process from a given white noise values list.
In the example we generate an AR(2) process Xt = 2 + 0.7Xt-1  - 0.1Xt-2  + Wt

Q source code 

w:"F"$ read0 `:whitenoise.txt  / the list of white noise values

a:2.0 / the constant term
c:-0.1 0.7 / the parameters of the ar model

Solution  
q)w  // the white noise terms
0.293 -0.554 -1.886 0.528 -0.58 -1.211 -1.036 -0.679 -1.665 -0.396

q)AR: {1 _ x, (y+ 2.0 + -0.1 0.7 wsum x)}
q)1 _' AR\[0 0;w]
0 2.293 3.0511 2.02047 3.637219 3.764006 3.060083 2.729657 ..

The above results can be verified here

Moving Average Process

An moving average process of order q, MA(q) is given by

Xt = a + c1Wt-1 + c2Wt-2 + ... + cqWt-q + Wt

where a is a constant term and Wt is white noise. The following Q code generates a MA(q) process from a given white noise values list.
In the example we generate an MA(2) process Xt = -2.0 + 0.6Wt-1  + 0.3Wt-2  + Wt

Q source code 

w:"F"$ read0 `:whitenoise.txt  / the list of white noise values

a:-2.0 / the constant term
c:0.6 0.3 / the parameters of the ar model

Solution  
q)w  // the white noise terms
0.293 -0.554 -1.886 0.528 -0.58 -1.211 -1.036 -0.679 -1.665 -0.396

q)MA:{[w] -2.0 + (2 _ w) + (0.3 0.6 wsum) each -1 _ 1 _  {1 _ x, y}\[0 0 ; w]}
q)MA[w]
-4.1305 -2.7698 -2.829 -3.4006 -3.9366 -3.6639 -4.3832 -3.5987 -2.4201.. 

Alternative Solution 1
q){-2.0 + x[y]+ 0.3 0.6 wsum x[(y-2), y-1]}[w;] each 2 _ til count w
-4.1305 -2.7698 -2.829 -3.4006 -3.9366 -3.6639 -4.3832 -3.5987 -2.4201.. 

Alternative Solution 2 (using sw function in previous section)
q)-2+(0.3 0.6 1.0 wsum) each (2 _ sw[3;w])
-4.1305 -2.7698 -2.829 -3.4006 -3.9366 -3.6639 -4.3832 -3.5987 -2.4201..

Performance Comparison
q)w:1000000?10.0
q)\t MA[w]
1076   // using scan is faster!!
q)\t {-2.0 + x[y]+ 0.3 0.6 wsum x[(y-2), y-1]}[w;] each 2 _ til count w
1136
q)\t -2+(0.3 0.6 1.0 wsum) each (2 _ sw[3;w])
1105

The above results can be verified here

Autoregressive Moving-Average process

An autoregressive moving-average process combines an AR(p) model with an MA(q) model. The model is usually then referred to as the ARMA(p,q) model where p is the order of the autoregressive part and q is the order of the moving average part. It is defined as,

Xt = a + [c1Wt-1 + c2Wt-2 + ... + cqWt-q]  +  [k1Xt-1 + k2Xt-2 + ... + kpXt-p] + Wt

where a is a constant term and Wt is white noise. The following Q code generates a ARMA(p,q) process from a given white noise values list.
In the example we generate an ARMA(1,1) process Xt = 2.0 + Wt - 0.25Wt-1  + 0.5Xt-1 using the sliding window function sw in the previous section.

q)sw
{{1 _ x, y}\[x # 0; y]}
q)arma
{{[x;y] 1 _ x, 2.0 + (0.5 * x) + -0.25 1.0 wsum y}\[0.0 ;  1_sw[2;x]] }
q)arma[w]
1.37275
0.938875
3.468938
3.022469
2.445234
2.489367
2.824684
1.917092
2.978796
3.905398
4.408449
4.341474
...

The above results can be verified here


Newton Rhapson method using Scan function  

Let x2 = 612. Find x.

F(x) = x2-612
F'(x) = 2x

Q Code

q)f:{x- ((x*x)-612)%(2*x)}
q)f\[10]
10
35.6
26.39551
24.79064
24.73869
24.73863
24.73863

Fun with Google Charts

This example shows a quick hack of front end UI querying a K database with integrated google charts.

gcharts