Speed issues

Jun 22, 2011 at 11:04 AM
Edited Jun 22, 2011 at 11:07 AM

Hi,

I've been using mathnet.iridium as the basis of a regression program and I decided to update it to math.net numerics. The code (VB) that does the grunt work has been changed from

 InputArray = XMatrix.CopyToArray 'Then passed to separate function

 Dim TempMatrix1 As Matrix = Matrix.Create(InputArray).QRDecomposition.R

Dim TempMatrix2 As Matrix = Matrix.Create(InputArray).QRDecomposition.R

 Dim XXT As 

Matrix

Matrix2.Transpose()

TempMatrix1 = TempMatrix1.Inverse()

TempMatrix2 = TempMatrix2.Inverse()

XXT = TempMatrix1 * TempMatrix2 'for calculating standard errors

 ---------------------------------------------------------------------

 to (and thanks Marcus for the help on this)

Betas = Xmatrix.QR.Solve(YVector)

RMatrix=XMatrix.QR.R
XXT=RMatrix.TransposeThisAndMultiply(RMatrix).Inverse()

 

-----------------------------------------------------------

 

The only problem is that the program now runs at half the speed as previously which I don't understand. The XMatrix that I'm testing with is 9000*100 (approx). Using Iridium it takes about 10 seconds to run but using Numerics it now takes about 20.

 

I'm using ExcelDNA to port these functions into Excel where the user interrface is built and the matrices are all declared as type DenseMatrix.

 I'm a bit of a newbie to coding so I may just have done something daft, but if anyone can give me some advice on this I'd be grateful.

 

 Another interesting thing is that Iridium allows the inversion of the R Matrix from a QR decomposition, but Numerics doesn't. As R isn't square, I presume that Iridium defaults to calculating the Left or Right Inverse depending on whether for an m*n matrix  m>n (Left) or m<n (Right), but I'm not certain about this.

 

Thanks,

Andrew

 

 

Betas = XMatrix.Solve(YMatrix)

Jun 22, 2011 at 2:49 PM

I think the problem is that you are doing the QR decompostion twice:

Betas = Xmatrix.QR.Solve(YVector)
RMatrix=XMatrix.QR.R

try:
var qr =  Xmatrix.QR();
var betas =  qr.Solve(YVector);
RMatrix=qr.R;
XXT=RMatrix.TransposeThisAndMultiply(RMatrix).Inverse()

 

Jun 23, 2011 at 11:39 AM

Hi,

I tried changing the code but it made no difference to the execution speed. So I've just tried a speed comparison in a new project using the same matrix as before, just solving for the coefficients, not for the standard errors. I'm using ExcelDNA to port the functions into Excel as an add-in.

Numerics code:

Imports ExcelDna.Integration
Imports MathNet.Numerics.LinearAlgebra.Double

Public Class Numerics

    Public Shared Function NumericsRegression(ByVal XArray(,) As Double, ByVal YArray(,) As Double) As Double(,)

        Dim XMatrix As Matrix = New DenseMatrix(XArray)
        Dim YMatrix As Matrix = New DenseMatrix(YArray)

        Dim Betas As Matrix

        Betas = XMatrix.QR.Solve(YMatrix)

        Return Betas.ToArray

    End Function


End Class

------------------------------------------------------------------------------------------------------------------------------

Iridium Code:

Imports MathNet.Numerics.LinearAlgebra
Imports ExcelDna.Integration

Public Class Iridium

    Public Shared Function IridiumRegression(ByVal XArray(,) As Double, ByVal YArray(,) As Double) As Double(,)

        Dim XMatrix As Matrix = Matrix.Create(XArray)
        Dim YMatrix As Matrix = Matrix.Create(YArray)

        Dim Betas As Matrix

        Betas = XMatrix.Solve(YMatrix)

        Return Betas.CopyToArray

    End Function

End Class

--------------------------------------------------------------------------------------------

I then set up a VBA routine in Excel to make the two functions evaluate 10 times and return the time taken. The Iridium based function took about 3.2 seconds, while the Numerics one took 69 seconds. I repeated this several times, always with the same result.

Any ideas? I'm happy to send someone my workbook if they want a closer look - I'm just stumped!

Thanks,

Andrew

Jun 23, 2011 at 2:41 PM
Edited Jun 23, 2011 at 5:24 PM

I think the problem is that Iridium is using "thin" QR and Numerics is doing "full" QR (see http://en.wikipedia.org/wiki/QR_decomposition under Rectangular matrices or "Matrix Computations" section 5.2.6 for a description on thin QR). 

Any objections to using Iridium's QR method (open question to everyone)? 

Jun 23, 2011 at 3:06 PM

Purely from my perspective the speed difference would prevent me from moving completely to Numerics from Iridium.

My reading of section 5.2.6 is that for an ill-conditioned problem then small changes in the matrix A would lead to relatively large changes in the solution. I think this is tolerable as if the problem is ill-conditioned then you have bigger problems anyway.

Another advantage with the thin method is that R becomes an n*n matrix as opposed to an m*n, therefore allowing the inverse to be created (useful, as discussed here: http://mathnetnumerics.codeplex.com/discussions/262045).

Could both be kept as e.g., QR and QRfull, or is that more trouble than it's worth?

 

 

Jun 23, 2011 at 5:20 PM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.