Quote:
Originally Posted by Ether
Here's the Delphi code. I wonder how fast it would run on a modern 64-bit machine. Maybe somebody would like to port it to C and try it.
|
Based on some PMs I have received, I should clarify a few things.
- The posted Delphi code reads the raw 8-column (r1 r2 r3 b1 b2 b3 rs bs) whitespace-delimited alliance scores text data file (from cached RAM) and constructs two matrices [At] and [b]. It takes ~12ms to do this on an 8-year-old Pentium D machine.
- [A]=[At]' is the the binary design matrix
- [b] is the matrix of alliance scores (not the team OPR scores)
- [A][x]≈[b] is the overdetermined system of linear equations
- [A][x]≈[b] can be solved with one line of code in Octave (or MatLab) as follows: [x]=[A]\[b]. [x] will be the matrix whose column vectors minimize the sum of the squares of the corresponding column vectors in the residuals matrix [r]=[b]-[A][x]
- But it is much faster (and acceptably stable and accurate for OPR purposes) to create and solve the Normal Equations [N][x]=[d] instead
- [N] and [d] can be formed from [At] and [b] as follows: [N]=[At][At]' and [d]=[At][b]
- [N][x]=[d] can be solved with one line of code in Octave (or MatLab) as follows: [x]=[N]\[d]
- solving [N][x]=[d] is faster than solving [A][x]≈[b] because 1) [N] is a smaller matrix than [A], and 2) N is symmetric positive definite so Cholesky factorization can be used
- the computations [A]=[At]', N=[At][A], and [d]=[At][b] take about 20ms on the 8-year-old Pentium D machine
- the Normal Equations solution [x]=[N]\[d] takes about 210ms on the 8-year-old Pentium D machine, using a single core
- there may be Cholesky factoring algorithms which would permit multiple cores to be used for factoring
See this post for some additional details:
http://www.chiefdelphi.com/forums/sh...00#post1404300