View Single Post
  #5   Spotlight this post!  
Unread 18-12-2014, 15:29
Ether's Avatar
Ether Ether is offline
systems engineer (retired)
no team
 
Join Date: Nov 2009
Rookie Year: 1969
Location: US
Posts: 8,141
Ether has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond reputeEther has a reputation beyond repute
Re: OPR Programming Challenge

Quote:
Originally Posted by Ether View Post
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