Chunky and equal-spaced polynomial multiplication

Finding the product of two polynomials is an essential and basic problem in computer algebra. While most previous results have focused on the worst-case complexity, we instead employ the technique of adaptive analysis to give an improvement in many “easy” cases. We present two adaptive measures and methods for polynomial multiplication, and also show how to effectively combine them to gain both advantages. One useful feature of these algorithms is that they essentially provide a gradient between existing “sparse” and “dense” methods. We prove that these approaches provide significant improvements in many cases but in the worst case are still comparable to the fastest existing algorithms.     

Simultaneous modular reduction and Kronecker substitution for small finite fields

We present algorithms to perform modular polynomial multiplication or a modular dot product efficiently in a single machine word. We use a combination of techniques. Polynomials are packed into integers by Kronecker substitution; several modular operations are performed at once with machine integer or floating point arithmetic; normalization of modular images is avoided when possible; some conversions back to polynomial coefficients are avoided; the coefficients are recovered efficiently by preparing them before conversion. We discuss precisely the required control on sizes and degrees. We then present applications to polynomial multiplication, prime field linear algebra and small extension field arithmetic, where these techniques lead to practical gains of quite large constant factors.     

Sparse polynomial division using a heap

In 1974, Johnson showed how to multiply and divide sparse polynomials using a binary heap. This paper introduces a new algorithm that uses a heap to divide with the same complexity as multiplication. It is a fraction-free method that also reduces the number of integer operations for divisions of polynomials with integer coefficients over the rationals. Heap-based algorithms use very little memory and do not generate garbage. They can run in the CPU cache and achieve high performance. We compare our C implementation of sparse polynomial multiplication and division with integer coefficients to the routines of the Magma, Maple, Pari, Singular and Trip computer algebra systems.     

The impulse analysis of the T-S fuzzy singular system via Kronecker index

The problem of impulse analysis is considered for the T-S fuzzy singular system by using the Kronecker index and the generalised Kronecker index in this paper. The T-S singular system is divided into two cases: the uniformly regular T-S fuzzy singular system and the non-uniformly regular T-S fuzzy singular system. The contribution of this paper is twofold. First, a new definition of the generalised Kronecker form is introduced, and the algorithm of finding the generalised Kronecker form is given. Second, two theorems are proved, one is that the uniformly regular T-S fuzzy singular system is impulsive if and only if the Kronecker index is greater than one, the other one is the non-uniformly regular T-S fuzzy singular system is impulsive if and only if the generalised Kronecker index is greater than one. Finally, two numerical simulations and the population model with stage structure are carried out to show the consistency with theoretical analysis and illustrate the effectiveness of the algorithm.     

一种改进的小矩阵连乘算法

首先引入了矩阵的连乘优先因子,接着采用连乘优先因子最小的贪心选择策略,提出了最小连乘因子优先算法。它确定125的连乘次序不一定是最优次序,但在确定连乘次序方面比动态规划法花费的时间和空间少。最后通过实例对比测试,表明该算法在计算小矩阵连乘时,总体效率优于动态规划法。     

On problems without polynomial kernels

Kernelization is a strong and widely-applied technique in parameterized complexity. A kernelization algorithm, or simply a kernel, is a polynomial-time transformation that transforms any given parameterized instance to an equivalent instance of the same problem, with size and parameter bounded by a function of the parameter in the input. A kernel is polynomial if the size and parameter of the output are polynomially-bounded by the parameter of the input.In this paper we develop a framework which allows showing that a wide range of FPT problems do not have polynomial kernels. Our evidence relies on hypothesis made in the classical world (i.e. non-parametric complexity), and revolves around a new type of algorithm for classical decision problems, called a distillation algorithm, which is of independent interest. Using the notion of distillation algorithms, we develop a generic lower-bound engine that allows us to show that a variety of FPT problems, fulfilling certain criteria, cannot have polynomial kernels unless the polynomial hierarchy collapses. These problems include k-Path, k-Cycle, k-Exact Cycle, k-Short Cheap Tour, k-Graph Minor Order Test, k-Cutwidth, k-Search Number, k-Pathwidth, k-Treewidth, k-Branchwidth, and several optimization problems parameterized by treewidth and other structural parameters.     

Solving the generalized Sylvester matrix equation AV +BW = VF via Kronecker map

This note considers the solution to the generalized Sylvester matrix equation AV ＋ BW = VF with F being an arbitrary matrix, where V and W are the matrices to be determined. With the help of the Kronecker map, an explicit parametric solution to this matrix equation is established. The proposed solution possesses a very simple and neat form, and allows the matrix F to be undetermined.     

Montgomery模乘算法的改进及其应用

Montgomery算法是目前最适合于通用处理器软件实现的大整数模乘算法。1996年,Koc总结了该算法的五种实现方法：SOS、CIOS、FIOS、FIPS和CIHS,并指出CIOS方法综合性能较优。首先深入分析了FIOS实现方法,并通过消除进位传递和减少循环控制等手段,提出了一种改进方法IFIOS。然后将该方法应用于模幂计算,给出了基于滑动窗口技术的Montgomery模幂算法。最后理论分析和实验结果表明,该改进将FIOS的执行速度提高了约54%,与目前常用的CIOS方法相比,亦有较大的优势。     

Polynomial multiplication on systolic arrays

In this article, we show how the multiplication of polynomials can be performed in a pipelined fashion on a systolic array in linear time steps. The computational model consists of two linear systolic arrays with 2(n+1) processing elements used and (m+2n+2) running time steps needed, where m, n are the degrees of the two given polynomials, respectively. Since the same types of processing elements execute the same program, it is suitable for VLSI implementation. This algorithm is also proved to be correct.     

Lower bounds for the multiplicative complexity of matrix multiplication

We prove a lower bound of km + mn + k—m + n— 3 for the multiplicative complexity of the multiplication of -matrices with -matrices using the substitution method. Received: July 8, 1997.     

椭圆曲线上点的数乘的一种固定窗口算法

椭圆曲线密码体制是公钥密码体制研究的热点。计算椭圆曲线上点的数乘是椭圆曲线密码算法的基础。固定窗口算法利用大整数s的2^u进制表示和适量的预计算,减少椭圆曲线上点的加法运算,从而加快椭圆曲线上点的数乘的运算速度。介绍了利用混合坐标思想,减少有限域上求逆运算的次数,对固定窗口算法进行局部优化的方法。最后给出了固定窗口算法的复杂性分析,并讨论了窗口宽度的最佳选取。     

基于Montgomery的分段并行标量乘快速算法

在椭圆曲线二进制域上,Montgomery算法利用在计算kP过程中只需计算x坐标,在最后才恢复y坐标的特性,使该算法的计算量更少。在此基础上提出基于Montgomery的分段并行标量乘算法来更进一步提高算法的效率,经分析,将整数标量分两段并行计算,算法效率可提高约25%,将其分三段时其效率可提高约37%。通过编程实现验证了新算法的效率确实有明显提高,新算法对椭圆曲线标量乘快速实现有实际意义。     

Fast parallel polynomial division via reduction to triangular toeplitz matrix inversion and to polynomial inversion modulo a power

It is known that division with a remainder of two polynomials of degree at most s can be performed over an arbitrary field F of constants using uniform arithmetic and Boolean circuits of depth O(log s log log s) and polynomial size. A new algorithm is presented that yields those bounds via reduction to triangular Toeplitz matrix inversion and to polynomial inversion modulo a power. (If|F| > (s?1)² or if P-uniform computation is allowed, then the depth can be reduced to O(log s).) This approach is new and makes the result conceptually simpler.     

一种抗侧信道攻击椭圆曲线标量乘算法的设计与实现

有限域 上点乘运算是影响椭圆曲线密码实现效率的关键运算之一。为提高椭圆曲线密码算法计算的安全性和效率性,从分析固定基点梳形算法（Fixed-base Comb算法）的特点出发,在现有的边信道攻击和标量乘算法的基础上,提出了一种新的标量乘算法——DF-Comb（Distance Fixed-base Comb）算法。新的算法对私钥（ ）重新设计编码、分组计算,在预计算阶段和赋值阶段进行改进,能够极大地提高算法计算阶段的效率;此外,考虑到算法的抗侧信道攻击能力,通过引入乘数分解技术来隐藏算法中相关侧信道信息,引入一种同时多标量乘算法用来提高了抗侧道攻击力,从而增强算法的安全性。仿真实验结果显示,改进的DF-Comb算法算法可以在提高计算效率的同时降计算的存储量。经算法实验比较分析研究,表明该算法能较好地抵抗多种侧信道攻击。     

一种基于De Bruijn网络结构的并行矩阵乘算法

在De Bruijn网络中进行并行矩阵乘法运算,算法简单,容易实现。首先介绍了De Bruijn网络结构,然后提出了一种基于De Bruijn网络结构的矩阵乘法的并行算法,分析了它的加速比、效率等性能及可扩展性,通过与Cannon算法的比较,证明它的时间复杂度等效于Cannon算法,最后通过实验验证了这个结论的正确性。     

The Mailman algorithm: A note on matrix-vector multiplication

Given an m×n matrix A we are interested in applying it to a real vector x∈Rn in less than the straightforward O(mn) time. For an exact deterministic computation at the very least all entries in A must be accessed, requiring O(mn) operations and matching the running time of naively applying A to x. However, we claim that if the matrix contains only a constant number of distinct values, then reading the matrix once in O(mn) steps is sufficient to preprocess it such that any subsequent application to vectors requires only O(mn/log(max{m,n})) operations. Algorithms for matrix-vector multiplication over finite fields, which save a log factor, have been known for many years. Our contribution is unique in its simplicity and in the fact that it applies also to real valued vectors. Using our algorithm improves on recent results for dimensionality reduction. It gives the first known random projection process exhibiting asymptotically optimal running time. The mailman algorithm is also shown to be useful (faster than naïve) even for small matrices.     

A fast cellular method of matrix multiplication

This paper proposes a cellular method of matrix multiplication. The method reduces the multiplicative and additive complexities of well-known matrix multiplication algorithms by 12.5%. The computational complexities of cellular analogs of such algorithms are estimated. A fast cellular analog is presented whose multiplicative and additive complexities are equal to ≈0.382n³ multiplications and ≈1.147n³ additions, respectively, where n is the order of the matrices being multiplied. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 55–59, May–June 2008.