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.     

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.     

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.     

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.     

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.     

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

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

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.     

一种乘同余伪随机序列快速实现的FPGA设计

针对一类乘同余运算,提出了一种快速算法。采用1个32位乘法、2个32位加法、少量移位操作和1个最高位分离操作方法,避免了连续减法和除法运算。采用硬件语言设计了快速算法。在此算法的基础上,设计了基于FPGA的伪随机序列发生器。     

A faster polynomial algorithm for 2-cyclic robotic scheduling

This paper addresses the 2-cyclic identical part scheduling in a no-wait robotic flowshop where exactly two parts enter and two parts leave the production line during each cycle. This problem was previously proved to be polynomially solvable in O(N⁸log N) time, where N is the number of tanks in the production line. This paper proposes an improved algorithm with reduced complexity O(N⁵log N).     

A polynomial fuzzy neural network for modeling and control

This paper introduces a novel neurofuzzy system based on polynomial fuzzy neural network (PFNN) architecture. A PFNN consists of a set of if-then rules with appropriate membership functions (MFs) whose parameters are optimized via a hybrid genetic algorithm. A polynomial neural network is employed in the defuzzification scheme to improve output performance and to select appropriate rules. A performance criterion for model selection is defined to overcome the overfitting problem in the modeling procedure. For a performance assessment of the PFNN inference system, two well-known problems are employed for a comparison with other methods. The results of these comparisons show that the PFNN inference system out-performs the other methods and exhibits robustness characteristics. This work was presented in part at the Fourth International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–22, 1999     

Solvability of systems of polynomial congruences modulo a large prime

We consider the following polynomial congruences problem: given a prime p, and a set of polynomials of total degree at most d, solve the system for solution(s) in . We give a randomized algorithm for the decision version of this problem. For a fixed number of variables, the sequential version of the algorithm has expected time complexity polynomial in d, m and log p; the parallel version has expected time complexity polylogarithmic in d, m and p, using a number of processors, polynomial in d, m and log p. The only point which prevents the algorithm from being deterministic is the lack of a deterministic polynomial time algorithm for factoring univariate polynomials over . Received: April 9, 1997.     

A polynomial algorithm for multi-robot 2-cyclic scheduling in a no-wait robotic cell

This paper addresses the multi-robot 2-cyclic scheduling problem in a no-wait robotic cell where exactly two parts enter and leave the cell during each cycle and multiple robots on a single track are responsible for transporting parts between machines. We develop a polynomial algorithm to find the minimum number of robots for all feasible cycle times. Consequently, the optimal cycle time for any given number of robots can be obtained with the algorithm. The proposed algorithm can be implemented in O(N⁷) time, where N is the number of machines in the considered robotic cell.     

Efficient uncertainty quantification with the polynomial chaos method for stiff systems

The polynomial chaos (PC) method has been widely adopted as a computationally feasible approach for uncertainty quantification (UQ). Most studies to date have focused on non-stiff systems. When stiff systems are considered, implicit numerical integration requires the solution of a non-linear system of equations at every time step. Using the Galerkin approach the size of the system state increases from n to S × n, where S is the number of PC basis functions. Solving such systems with full linear algebra causes the computational cost to increase from O(n³) to O(S³n³). The S³-fold increase can make the computation prohibitive. This paper explores computationally efficient UQ techniques for stiff systems using the PC Galerkin, collocation, and collocation least-squares (LS) formulations. In the Galerkin approach, we propose a modification in the implicit time stepping process using an approximation of the Jacobian matrix to reduce the computational cost. The numerical results show a run time reduction with no negative impact on accuracy. In the stochastic collocation formulation, we propose a least-squares approach based on collocation at a low-discrepancy set of points. Numerical experiments illustrate that the collocation least-squares approach for UQ has similar accuracy with the Galerkin approach, is more efficient, and does not require any modification of the original code.     

Efficient 3-dimensional GLV method for faster point multiplication on some GLS elliptic curves

We discover that two distinct efficient endomorphisms can both exist on some Galbraith-Lin-Scott (GLS) elliptic curves Galbraith et al. (2009) [4]. By using them we generalize the Gallant-Lambert-Vanstone (GLV) method Gallant et al. (2001) [5] for faster point multiplication on these curves to dimension 3, and give some implementation result which shows that our 3-dimensional GLV (3GLV) method runs in 0.897 the time of 2-dimensional GLV (2GLV) method as Galbraith et al. did in Galbraith et al. (2009) [4] for the point multiplication on these curves.     

基于高基阵列乘法器的高速模乘单元设计与实现

蒙哥马利模乘算法是最适合硬件实现的模乘算法,被应用在RSA密码和ECC密码的协处理器设计中.目前性能最高的是高基蒙哥马利模乘算法,分析了高基蒙哥马利算法的实现,提出了一种新的基于高基阵列乘法器的Montgomery模乘高速硬件实现结构,基于这种结构位长为n的比特模乘仅需要约n/w+6个时钟周期,该结构设计的电路只与最小单元有关,在硬件实现时可以大大提高频率,并提高设计的性能,可以设计高速的RSA和椭圆曲线密码大规模集成电路.