sql-server - 如何通过 SQL 确定矩阵是否为 'positive definite'？

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 以一种相当黑盒的方式处理确定。如果我有一个可以输入 Assets 、相关 Assets 和值(value)的 SQL 表，有没有办法进行数学计算？

我查了一些，我还没有真正在 MSSQL 中看到任何处理矩阵数学的东西。

谢谢。

编辑:Microsoft SQL 2008

Answer 1

好的，我们开始。这行得通，但确实给人一种感觉，我们不得不强制 SQL Server 去做它并不真正想做的事情。我不愿意在现实生活中推荐这样做 - 它会扩展为 O(n^3)在矩阵大小方面，我相当确定。也许有更好的方法，做 Cholesky decomposition而不是这种方式 - 我可能会在以后研究这个。说完警告，让我们继续:

这需要 SQL Server 2008，用于其 table数据类型

(即使这样也不能提供尽可能有用的帮助，正如我们将看到的......)

首先，方法。我们将使用 Sylvester's criterion ，因为它最容易理解:当所有主要次要的行列式为正时，实对称矩阵是 PD。所以我们需要一种计算行列式的方法。同样，我们将使用一种简单的方法 ( Laplace expansion ) 而不是任何旨在提高计算效率的方法。

基础工作

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

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

计算决定因素

为此，我们将定义两个相互递归的函数，因为鉴于 table 的功能有限，这是我使其工作的唯一方法。在 SQL 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

我们现在准备使用 Laplace expansion 递归计算行列式.这涉及调用我们的相互递归的同志，它将根据我们请求的行和列进行次要，然后再调用我们计算次要的行列式

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

有了行列式计算器，我们就快到了。

测试正定性

根据 Sylvester's criterion ，一个矩阵是 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)

这些结果与我从 this online calculator 得到的结果一致，所以我很高兴这有效。

时间安排

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

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

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

注意事项

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

以这种简单的方式计算行列式的执行时间随着 O(n^3) 增长在矩阵大小

此代码重复计算相同的值，但不进行内存

绝对没有健全性或错误检查 - 例如，一个不是正方形的矩阵，或 Matrix 中的值没有意义的输入值会导致所有东西都落入堆

我没有考虑数值稳定性，这是现实世界数值计算的必须

也就是说，这是一个有趣的练习，希望能给你一些有用的指导，让你了解在现实生活中如何实际处理这个问题。

也许我会考虑使用 Cholesky decomposition 来做这件事稍后...