本文同时处理公式的快速和就地算法,其中结果必须线性累积:一些输出变量也是输入变量,由线性依赖关系链接。 基本示例包括多项式或矩阵的就地累积乘法(只有O(1)的额外空间)。 困难在于将现场计算与快速算法相结合:这些计算通常以牺牲(可能很大)额外的临时空间为代价。 我们首先为任何双线性公式(因此对于多项式和矩阵乘法)提出了一种新的快速和现场积累算法的自动设计,然后将其扩展到函数集合的任何线性积累。 为此,我们将内部模型放宽到允许修改其输入的任何算法,前提是这些输入随后恢复到初始状态。 这使我们能够为快速多项式乘法和类似Strassen的矩阵乘法派生出就地积累算法。 然后,我们考虑同时快速和到位的计算欧几里定公的剩余部分R = A B。 如果 A 和 B 具有相应的度 m+n 和 n,并且 M(k) 表示(不位)算法乘以两个度-k多项式的复杂性,则我们的算法最多使用 O(n/m) log(m)log(m)) 算术运算。 如果 M(n) = Θ(n^1+ε) 对于一些 ε>0,那么我们的算法确实匹配了 O(n/m) M(m) 的不位置复杂边界。 我们还提出了计算 - 仍在原地并具有相同的复杂边界的变体 - A = A B,R += A B和R += AC B,这是有限场扩展中的乘法。 为了实现这一目标,我们开发了Toeplitz矩阵操作的技术,用于广义卷积,短产品和功率序列划分以及输出也是输入的一部分的剩余部分。