Chief Delphi
Page 3 of 5 < 12 3 45 >
Show 100 post(s) from this thread on one page

Chief Delphi (http://www.chiefdelphi.com/forums/index.php)
-   Scouting (http://www.chiefdelphi.com/forums/forumdisplay.php?f=36)
-   -   OPR Formula (http://www.chiefdelphi.com/forums/showthread.php?t=101390)

Ether 31-01-2012 18:58
Re: OPR Formula
 
Quote:
Originally Posted by Ed Law (Post 1117250)
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 used1?

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.

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

Ed Law 31-01-2012 23:54
Re: OPR Formula
 
1 Attachment(s)
Quote:
Originally Posted by Ether (Post 1117327)
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 used1?

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.

1 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 01-02-2012 00:56
Re: OPR Formula
 
Quote:
Originally Posted by Ed Law (Post 1117594)
I have attached the data I used. I am sure we will get the same results.
Yup. Identical.

Quote:
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.

Quote:
The algorithm I used was implemented by Sergey Bochkanov at the University of Tennessee
Would that be ALGLIB ?

JewishDan18 01-02-2012 01:32
Re: OPR Formula
 
Quote:
Originally Posted by brennonbrimhall (Post 1115315)
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 :P

Ed Law 01-02-2012 01:54
Re: OPR Formula
 
Quote:
Originally Posted by Ether (Post 1117638)
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 03-02-2012 11:19
Re: OPR Formula
 
Quote:
Originally Posted by brennonbrimhall (Post 1115315)
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 database1.

There are several different methods for finding an approximate solution to an overdetermined system of linear equations1, 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:

Code:
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]


1 I can provide the details if anyone's interested

2 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.

3 [P]=[A]T[A] will be symmetric positive definite

MarkOfDinosaur 04-02-2012 17:06
Re: OPR Formula
 
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 04-02-2012 17:59
Re: OPR Formula
 
1 Attachment(s)
Quote:
Originally Posted by MarkOfDinosaur (Post 1119942)
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 04-02-2012 20:17
Re: OPR Formula
 
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 04-02-2012 20:27
Re: OPR Formula
 
Quote:
Originally Posted by Tom Line (Post 1120085)
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 04-02-2012 22:33
Re: OPR Formula
 
1 Attachment(s)

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 it1?

Thank you.



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

Tom Line 05-02-2012 00:02
Re: OPR Formula
 
Excel 2010, 5 minutes 30 seconds.

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

Ether 05-02-2012 00:28
Re: OPR Formula
 
1 Attachment(s)
Quote:
Originally Posted by Tom Line (Post 1120254)
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 06-02-2012 22:22
Re: OPR Formula
 
Quote:
Originally Posted by Ether (Post 1119962)
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 06-02-2012 23:12
Re: OPR Formula
 
Quote:
Originally Posted by MarkOfDinosaur (Post 1121387)
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?


All times are GMT -5. The time now is 04:18.
Page 3 of 5 < 12 3 45 >
Show 100 post(s) from this thread on one page

Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi