OPR Formula

[Ether]

Originally Posted by Ed Law

Ether,

Your republished numbers are very close to mine now. I also used double precision. My implementation is done in Excel using VBA. I do not actually put the 2053 X 2053 matrix inside the spreadsheet so it works in older version. The program read in the match results and assemble the matrix. It is just stored in the memory for the calculation. Solving the equations inside Excel using VBA is probably slower than outside in another app. Tom Line mentioned they are solving the equations using Excel built-in solver. I am curious what algorithm they use and how fast that would be.

How come you only have 2052 teams? I have 2053 teams in 2011.

Column " B" of the "Worldrank" tab of your Team_2834 2011_Scouting_Database Championship v4b.xls spreadsheet has
has teams 1366 and 2627 which were not in Phil's file. Phil's file has team 1702 which is not in your spreadsheet. So we still aren't using the same data. Do you have (or could you quickly generate) a single file in XLS, CSV, fixed-field, or whitespace-delimited format which has all the data you used¹?

Matrix factor time for double-precision 2052x2052 matrix elements with double-precision intermediate calculations (instead of Intel extended precision 80-bit) is 12.4 seconds.

I didn't know that the Solver could be used by a macro to operate on a matrix in memory. I'll have to look into that. Even so, I'm surprised that they let you solve a 2052x2052 matrix using Solver. The Solver in Excel is a limited (but still quite capable) version of a commercial product from a third party named Frontline.

¹ with fields red1, red2, red3, blue1, blue2, blue3, red_alliance_score, blue_alliance_ score

[Ed Law]

Originally Posted by Ether

Column " B" of the "Worldrank" tab of your Team_2834 2011_Scouting_Database Championship v4b.xls spreadsheet has
has teams 1366 and 2627 which were not in Phil's file. Phil's file has team 1702 which is not in your spreadsheet. So we still aren't using the same data. Do you have (or could you quickly generate) a single file in XLS, CSV, fixed-field, or whitespace-delimited format which has all the data you used¹?

Matrix factor time for double-precision 2052x2052 matrix elements with double-precision intermediate calculations (instead of Intel extended precision 80-bit) is 12.4 seconds.

I didn't know that the Solver could be used by a macro to operate on a matrix in memory. I'll have to look into that. Even so, I'm surprised that they let you solve a 2052x2052 matrix using Solver. The Solver in Excel is a limited (but still quite capable) version of a commercial product from a third party named Frontline.

¹ with fields red1, red2, red3, blue1, blue2, blue3, red_alliance_score, blue_alliance_ score

1702 registered for Los Angeles Regional but did not compete. 1366 did compete at Los Angeles Regional. 2627 is a Michigan team and attended Ann Arbor district last year.
I have attached the data I used. I am sure we will get the same results.
I did not use the Excel build in Solver. The algorithm I used was implemented by Sergey Bochkanov at the University of Tennessee

[Ether]

Originally Posted by Ed Law

I have attached the data I used. I am sure we will get the same results.

Yup. Identical.

I did not use the Excel build in Solver.

Yes, I understood that. The remark in my previous post about Solver was in reference to your earlier post mentioning that Tom Line was using Solver.

The algorithm I used was implemented by Sergey Bochkanov at the University of Tennessee

Would that be ALGLIB ?

[JewishDan18]

Originally Posted by brennonbrimhall

This is going to sound extremely stupid, but what is the formula for OPR?

Thanks in advance.

If you find me some time, I can whiteboard you through it

[Ed Law]

Originally Posted by Ether

Yup. Identical.



Yes, I understood that. The remark in my previous post about Solver was in reference to your earlier post mentioning that Tom Line was using Solver.



Would that be ALGLIB ?

Yes, it is.

[Ether]

Originally Posted by brennonbrimhall

This is going to sound extremely stupid, but what is the formula for OPR?

The "short" answer is, the "formula" for OPR is

[A][OPR]~[SCORE]

...where OPR for a given team is one of the N elements of the [OPR] Nx1 column vector approximate solution to the overdetermined system of linear equations shown above. N is the number of teams, M is the number of matches, and [SCORE] is a (2M)x1 column vector of alliance scores for each match in the database being used to do the computation. [A] is a (2M)xN matrix generated from the database¹.

There are several different methods for finding an approximate solution to an overdetermined system of linear equations¹, but for this particular problem using Normal Equations and Cholesky factorization to find the least squares solution is perhaps the most common.

Normal Equations solution method:

Multiply both sides of [A][OPR]~[SCORE] by the transpose of [A]:

[A]T[A][OPR]=[A]T[SCORE]

which can be re-written as

[P][OPR]=[S]     (see footnote 2 below)

...where [P]=[A]T[A] and [S]=[A]T[SCORE]

then use Cholesky factorization (see footnote 3 below)
to find the lower triangular matrix [L] such that

[L][L]T=[P]

to get

[L][L]T[OPR]=[S]

now substitute [y] for [L]T[OPR] to get

[L][y]=[S]

and use forward substitution to solve for [y]

then, with [y] known, use backward substitution to solve

[L]T[OPR]=[y]

for [OPR]

¹ I can provide the details if anyone's interested

² The matrix [P] and the vector [S] can be constructed directly from the database, rather than constructing [A] and [SCORES]. In fact, doing so is quicker and requires less memory. I show all the steps in order to make it clear that [OPR] is an approximate solution to the overdetermined data in the database, and that approximate solutions other than least squares are possible.

³ [P]=[A]^T[A] will be symmetric positive definite

[MarkOfDinosaur]

I am having trouble understanding OPR. I had thought I had gotten it, but my results seem wrong. I'm pretty sure the problem lies with how i am performing the cholesky decomposition. I don't understand how to make a macro for it. I have looked into Ed Law's workbooks, but I still don't understand. Would it be possible for someone to explain how cholesky decomposition works, or is that too complicated?
Thanks

[Ether]

Originally Posted by MarkOfDinosaur

I am having trouble understanding OPR. I had thought I had gotten it, but my results seem wrong. I'm pretty sure the problem lies with how i am performing the cholesky decomposition. I don't understand how to make a macro for it. I have looked into Ed Law's workbooks, but I still don't understand. Would it be possible for someone to explain how cholesky decomposition works, or is that too complicated?
Thanks

Would you like to test your Cholesky implementation first to see if that is really the problem?

Attached is a 64x64 test matrix and its Cholesky factorization.

Both files are CSV so Excel should be able to open them directly.

[Tom Line]

We're actually using matrix functions built into excel - no solver and no VB. It's three or four different pages of calculations. The first is the data, the second is the data sorted into the matrix, then we do the inverse matrix function, and output the final OPR values.

While it isn't the example I used to create our spreadsheet, this page will show you exactly how we go about it. Only the newer versions (2010 and newer) will allow large enough matrices to do the math.

http://www.duncanwil.co.uk/simult.html

[Ether]

Originally Posted by Tom Line

We're actually using matrix functions built into excel - no solver and no VB. It's three or four different pages of calculations. The first is the data, the second is the data sorted into the matrix, then we do the inverse matrix function, and output the final OPR values.

While it isn't the example I used to create our spreadsheet, this page will show you exactly how we go about it. Only the newer versions (2010 and newer) will allow large enough matrices to do the math.

http://www.duncanwil.co.uk/simult.html

Hi Tom,

Just curious: How long does it take to invert a 2053x2053 matrix in Excel?

[Ether]

Attached is a 2053x2053 invertible matrix.

Would someone be willing to pull it into Excel 2010 (or newer) and test how long it takes to invert it¹?

Thank you.



¹how to invert a matrix in Excel: http://opim.wharton.upenn.edu/~guign...matrix_inv.pdf

[Tom Line]

Excel 2010, 5 minutes 30 seconds.

i3 core @ 2.13, 8 GB ram, windows 7 64 bit home premium.

[Ether]

Originally Posted by Tom Line

Excel 2010, 5 minutes 30 seconds.

i3 core @ 2.13, 8 GB ram, windows 7 64 bit home premium.

Thanks Tom.

An optimized Cholesky algorithm solves the 2053x2053 system in a little over 12 seconds on a 3.4GHz Pentium D with 1GB RAM 32bit WinXP Pro SP3.

[MarkOfDinosaur]

Originally Posted by Ether

Would you like to test your Cholesky implementation first to see if that is really the problem?

Attached is a 64x64 test matrix and its Cholesky factorization.

Both files are CSV so Excel should be able to open them directly.

Ok, it works, thanks. Now, where do I go from here?

[Ether]

Originally Posted by MarkOfDinosaur

Ok, it works, thanks. Now, where do I go from here?

What version of Excel do you have?

And just curious: where did you get your Cholesky algorithm from?