Хорошо, вот и мы. Это работает, но у нас возникает ощущение, что нам нужно заставить SQL Server делать то, чего он на самом деле не хочет. Я бы не стал рекомендовать делать это в реальной жизни - я уверен, что он будет масштабироваться как O(n^3) в размере матрицы. Возможно, есть лучший способ сделать разложение Холецкого , а не таким образом - я мог бы рассмотреть это позже. С оговорками, скажем, давайте продолжим:
Для этого требуется SQL Server 2008, для его table тип данных
(и даже это не настолько полезно, как могло бы быть, как мы увидим ...)
Во-первых, подход. Мы собираемся использовать критерий Сильвестра , поскольку его проще всего понять: реальная симметричная матрица - это PD, если детерминанты всех главных миноров положительны. Так что нам нужен способ расчета определителей. Опять же, мы собираемся использовать простой подход ( расширение Лапласа ), а не что-либо, предназначенное для вычислительной эффективности.
Groundwork
Мы начнем с определения пользовательского типа таблицы, который мы будем использовать для передачи матриц:
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
Теперь мы готовы рекурсивно вычислить определитель, используя расширение Лапласа . Это включает в себя вызов нашего взаимно-рекурсивного товарища, который будет уменьшаться до запрашиваемой строки и столбца, а затем перезвонит нам, чтобы вычислить определитель младшего
-- 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, которые не имеют смысла, приведут к падению всего в кучу
- Я не учел числовую стабильность, которая необходима для численных расчетов в реальном мире
Тем не менее, это интересное упражнение и, надеюсь, даст вам несколько полезных советов о том, как вы могли бы на самом деле подойти к этому в реальной жизни.
Возможно, я посмотрю на это, используя Разложение Холецкого на более поздний срок ...