好的,我们开始吧。这是可行的,但确实让人感觉我们必须加强对SQL Server的武装,让它做一些它真正不想做的事情。在现实生活中,我不愿意推荐这样做——它将扩展为
O(n^3)
在矩阵大小方面,我相当肯定。也许还有更好的办法
Cholesky decomposition
而不是这样-我以后可能会调查这个。鉴于上述警告,让我们继续:
这要求SQL Server 2008
table
数据类型
(即便如此,我们也无法像我们将看到的那样,提供尽可能多的帮助……)
第一,方法。我们要用
Sylvester's criterion
最容易理解的是:实对称矩阵是pd-iff,所有主要子式的行列式都是正的。所以我们需要一种计算行列式的方法。同样,我们将使用一种简单的方法(
Laplace expansion
)而不是为了计算效率而设计的任何东西。
地基工程
我们首先定义将用于传递矩阵的用户定义表类型:
create type Matrix
as table ( Row int, Col int, Val float )
go
计算行列式
对于这个,我们将定义两个相互递归的函数,因为这是我唯一能使它工作的方法,因为
桌子
在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
现在我们可以用
拉普拉斯扩张
. 这涉及到一个对我们相互递归的伙伴的调用,它将根据我们请求的行和列进行minorize,然后调用我们来计算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
事实证明
DeterminantOfMinor
非常简单,如果
桌子
值在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-iff,它的所有主要子式的行列式都是正的。所以我们可以构建一个(自)递归函数来检查这个问题,唯一的问题是它值得我们确保
便宜的
首先是行列式(较小的矩阵):
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
输入的值没有意义,将导致所有内容都落在一个堆中。
-
我没有考虑数值稳定性,这是实际数值计算的必要条件。
这就是说,这是一个有趣的练习,希望能给你一些有用的提示,告诉你如何在现实生活中真正做到这一点。
也许我会考虑用
胆石分解
以后的日子…
