Is there any way, purely in MSS开发者_开发技巧QL, to determine if the following maxtrix would calculate out as positive definite?

A C D G H I
A 1.00 0.68 0.24 0.62 0.90 0.00
C 0.68 1.00 0.25 0.46 0.61 0.00
D 0.24 0.25 1.00 0.60 0.08 0.00
G 0.62 0.46 0.60 1.00 0.46 0.00
H 0.90 0.61 0.08 0.46 1.00 0.00
I 0.00 0.00 0.00 0.00 0.00 1.00

Right now we're using a 3rd party app, ExtremeNumerics, to handle the determination in a rather blackbox way. If I had a SQL table that I could enter the assets, the correlated asset and the value, would there be a way to do the math?

I poked around some and I haven't really seen anything in MSSQL that handles matrix math.

thanks.

edit: Microsoft SQL 2008

Right, here we go. This works, but does give the feeling that we are having to strong-arm SQL Server into doing things it doesn't really want to. I'd be disinclined to recommend doing this in real life - it's going to scale as O(n^3) in matrix size, I'm reasonably sure. Perhaps there's a better way, doing Cholesky decomposition rather than this way - I might look into this at a later date. With the caveats out of the say, let's proceed:

This requires SQL Server 2008, for its table datatype

(and even that falls somewhat short of being as helpful as it might be, as we'll see...)

First, the approach. We're going to use Sylvester's criterion, as it's the easiest to understand: a real symmetric matrix is PD iff the determinants of all the principal minors are positive. So we'll need a way of calculating determinants. Again, we're going to use a simple approach (Laplace expansion) rather than anything designed for computational efficiency.

Groundwork

We start with defining the user-defined table type we're going to use to pass matrices around:

create type Matrix
as table ( Row int, Col int, Val float )
go

Calculating determinants

For this, we're going to define two mutually-recursive functions, because that was the only way I could make it work given the limited capabilities of table type data in SQL Server 2008.

First, the entry point (which also handles the base case):

create function Determinant ( @matrix Matrix readonly )
returns float
as
begin
    -- Base case of recursion
    if ((select count(*) from @matrix) = 1) 
        return (select Val from @matrix)

Having established we're not at the base case (a 1x1 matrix), we now have work to do. The first thing is to 'canonicalize' the row and column numbers in our input from whatever they are now to 1..n

    -- canonicalize row and col numbers (doesn't affect answer)
    declare @rowMap table ( fr_row int, to_row int )
    declare @colMap table ( fr_col int, to_col int )

    insert @rowMap
    select row, row_number() over(order by row) from @matrix
    group by row

    insert @colMap
    select col, row_number() over(order by col) from @matrix
    group by col

    declare @canonicalMatrix Matrix
    insert @canonicalMatrix 
    select 
        to_row, to_col, Val
    from @matrix m
    inner join @rowMap rm on m.row = rm.fr_row
    inner join @colMap cm on m.col = cm.fr_col

We're now ready to recursively compute the determinant using Laplace expansion. This involves a call out to our mutually-recursive comrade, which will minorize by the row and column we request, then call us back to compute the determinant of the minor

    -- apply laplace expansion on first row
    return
    (
        select sum(
            (case col % 2 
            when 1 then 1   -- odd col
            when 0 then -1  -- even col
            end
            )
                    * Val 
                    * dbo.DeterminantOfMinor ( @canonicalMatrix, 1, col ) 
            ) from @canonicalMatrix where row = 1
    )
end
go

As it turns out DeterminantOfMinor is very simple, and wouldn't be necessary if table values were more first-class in SQL Server:

create function dbo.DeterminantOfMinor ( 
    @matrix Matrix readonly
    , @drop_row int
    , @drop_col int 
)
returns float
as
begin

    declare @minor Matrix
    insert @minor select * from @matrix 
        where row <> @drop_row and col <> @drop_col
    return
        dbo.Determinant( @minor )

end
go

With a determinant calculator available, we're nearly there.

Testing for positive-definiteness

According to Sylvester's criterion, a matrix is PD iff the determinants of all its principal minors are positive. So we can build a (self-)recursive function to check this, the only twist being that it's worth making sure we do the cheap determinants (the smaller matrices) first:

create function dbo.is_positive_definite ( @matrix Matrix readonly )
returns bit
as
begin
    -- base case of recursion
    -- a 1x1 matrix is PD iff the single value is positive
    if ((select count(*) from @matrix) = 1) 
        return (select case when Val > 0 then 1 else 0 end from @matrix)

We build the matrix which is our input without its last row and column:

    declare @smallerMat Matrix
    insert @smallerMat
    select row, col, Val from @matrix
    where row < (select max(row) from @matrix)
    and col < (select max(col) from @matrix)

and recurse down, only computing the determinant of our input if all our principal minors are confirmed to be PD:

    -- for our input to be PD, its smaller version must be PD:
    return
        ( select case dbo.is_positive_definite( @smallerMat )
        when 1 then 
                (select case 
                     when dbo.Determinant ( @matrix ) > 0 
                     then 1 
                     else 0 
                     end)
        else 0
        end
        )

end
go

And that's it!

Testing

I used your sample:

declare @test Matrix

insert @test values ( 1, 1, 1.00 )
insert @test values ( 1, 2, 0.68 )
insert @test values ( 1, 3, 0.24 )
/* snip */
insert @test values ( 6, 4, 0.00 )
insert @test values ( 6, 5, 0.00 )
insert @test values ( 6, 6, 1.00 )

select dbo.Determinant ( @test )
select dbo.is_positive_definite ( @test )


----------------------
0.0333962320000001

(1 row(s) affected)


-----
1

(1 row(s) affected)

These results agree with what I got from this online calculator, so I'm happy this works.

Timings

Using the first n columns of your test data, on the system I tested on:

n   Time (s)
1   < 1
2   < 1
3   < 1
4   < 1
5   1
6   17

Worrying trend, I'm sure you'll agree. Hence my:

Caveats

I would regard this code as no more than a proof of concept:

• Execution time for calculating determinants in this naive fashion grows as O(n^3) in matrix size
• This code repeatedly calculates the same values doing no memoization
• There's absolutely no sanity- or error- checking - a matrix which is not square, for example, or values in the Matrix input value that don't make sense, will cause everything to fall in a heap
• I have given no consideration to numerical stability, which is a must for real-world numerical calculations

That said, it's an interesting exercise and hopefully will give you some useful pointers as to how you might actually approach this in real life.

Perhaps I'll look at doing it using Cholesky decomposition at a later date...