如何通过SQL确定矩阵是否为"肯定"？

Question

有什么办法,纯粹是MSSQL,以确定以下maxtrix将计算出正定？

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

现在我们正在使用第三方应用程序,ExtremeNumerics,来处理在一个相当黑箱方式的决心.如果我有一个SQL表,我可以输入资产,相关资产和价值,是否有办法进行数学运算？

我捅了一些,我还没有在MSSQL中看到任何处理矩阵数学的东西.

谢谢.

编辑:Microsoft SQL 2008

Answer 1

对,我们走了.这种方法很有效,但确实让人感觉我们必须强有力地将SQL Server用于做它不想要的事情.我不愿意在现实生活中推荐这样做 - 它会按照O(n^3)矩阵大小进行扩展,我有理由相信.也许有一种更好的方法,做Cholesky分解而不是这种方式 - 我可能会在以后对此进行研究.随着说法的警告,让我们继续:

这需要SQL Server 2008作为其table数据类型

(甚至有点不像它可能会有所帮助,我们会看到...)

一,方法.我们将使用西尔维斯特的标准,因为它是最容易理解的:如果所有主要未成年人的决定因素都是正的,那么真正的对称矩阵就是PD.所以我们需要一种计算决定因素的方法.同样,我们将使用一种简单的方法(拉普拉斯扩展),而不是任何为计算效率而设计的方法.

地基

我们首先定义我们将用于传递矩阵的用户定义表类型:

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

计算决定因素

为此,我们将定义两个相互递归的函数,因为考虑到tableSQL Server 2008 中类型数据的有限功能,这是我能够使它工作的唯一方法.

首先,入口点(也处理基本情况):

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)

确定我们不是基本情况(1x1矩阵),我们现在有工作要做.第一件事是将我们输入中的行号和列号"规范化",不管它们现在是什么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

我们现在准备使用拉普拉斯扩展递归计算行列式.这涉及到我们的相互递归的同志的召唤,它将按我们要求的行和列进行小规模化,然后打电话给我们来计算未成年人的决定因素

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

事实证明DeterminantOfMinor非常简单,如果table值在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

有了决定性计算器,我们几乎就在那里.

测试肯定性

根据西尔维斯特的标准,如果所有主要未成年人的决定因素都是正数,那么矩阵就是PD.所以我们可以建立一个(自我)递归函数来检查这个,唯一的转折是确保我们首先做廉价的决定因素(较小的矩阵)是值得的:

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)

我们构建了矩阵,它是我们的输入,没有最后一行和列:

    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)

如果我们所有的主要未成年人都被确认为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

就是这样!

测试

我用过你的样本:

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)

这些结果与我从这个在线计算器得到的结果一致,所以我很高兴这很有用.

计时

使用n测试数据的第一列,在我测试的系统上:

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

令人担忧的趋势,我相信你会同意的.因此我:

注意事项

我认为这段代码只不过是一个概念证明:

• 以这种天真的方式计算决定因素的执行时间O(n^3)与矩阵大小一样增长
• 此代码重复计算没有记忆的相同值
• 绝对没有完整性或错误检查 - 例如,一个非正方形的矩阵,或者Matrix输入值中没有意义的值,将导致所有内容都落入堆中
• 我没有考虑数值稳定性,这是现实世界数值计算的必要条件

也就是说,这是一个有趣的练习,希望能给你一些有用的指示,指出你在现实生活中如何实际接近这个.

也许我会考虑在以后使用Cholesky分解来做...