本文的其余部分组织如下。在第2节中,我们修正了一些符号,并回忆了一些
定义,包括史密斯标准形的定义。第三节考虑对非奇异
的
ARn
×
n
,计算
Smith分解:
A
=
snf(
A
),其中 n是R上
的
n
个
矩
阵。第4节定义并给出计算外积伴随公式的算法,外积伴随公式本质上是史密斯分
解
s
n
A
−
1
=
snf(
s
n
A
−
1
)。 第3节和第4节一般性地发展了结果,因此它们都适用
于
R
=
Z和
R
=
K
[
x
]。第五节给出了整数矩阵求逆的算法,第六节给出了多项式
矩阵的变分算法。偶然的是,我们可以应用一些简单的代数预处理技术,将原始d
次输入矩阵
A K
[
x
]
n
×
n
变换
为一个新的矩阵
B
,它
的行列式为
nd
。一旦通过外积
伴随公式确定了
B
的逆,则可以在分配的时间内反转预处理以恢复
A
的逆。
成本函数
设
M
:Z
>
0
R
>
0
使得可以
使用
t
个最
多
M
(
t
)位
运算
来乘以大小为2t的整数
。
S
_
h
_
nha g
e_Str a ss en a lg o rithm [2 1 ]
都有
M
(
t
)
= O
(
t
(
log t
)(
log log
t
))
. 我们假设
M
(
a
)
+
M
(
b
)
≤
M
(
a
+
b
)和
M
(
ab
)
≤
M
(
a
)
M
(
b
),
其中
a
,
b
N
≥
2
。我们参考[6,8.3节]以获得更多关于整数乘法的参考和讨论。
定义一个额外的函数
B
来限制与整数gcd相关的计算的成本将是有用的。我们可
以取
B
(
t
)
=
M
(
t
)log
t
。然后,扩展的gcd问题的两个整数的大小有界的2
t
,和有
理数重建问题[6,5.10节]的模有界的2
t
,可以解决
O
(
B
(
t
))域操作[20](与[19]
相比)。
我们将稍微重载符号,并使用
M
:Z
≥
0
R
>
0
作为多项式乘法的代价函数:两个次
数为
d
的
K
[
x
]中的多项式最多可以使用
M
(
d
)个域运算相乘。类似地,
B
将被用
作与gcd相关的问题的成本函数,如有理函数重构和扩展的gcd。与整数情况类
似,我们可以取
B
(
d
)
=
M
(
d
)log
d
。我们参考[6,11.1节]了解更多细节和参
考。
2
定义、符号和术语
设
R
是一个主理想环,一个有单位元的交换环,其中每个理想都是主-NR。本文主
要研究整环
R
=
Z和
R
=
K
[
x
].在[17]之后,我们规定了一个完整的非结合集A(
R
),
并且对于每个非零
s
∈
R
,规定了一个完整的剩余集
R
(
R
,
s
),如下所示。
(四)