Computations with quasiseparable polynomials and matrices

In this paper, we survey several recent results that highlight an interplay between a relatively new class of quasiseparable matrices and univariate polynomials. Quasiseparable matrices generalize two classical matrix classes, Jacobi (tridiagonal) matrices and unitary Hessenberg matrices that are known to correspond to real orthogonal polynomials and Szegö polynomials, respectively. The latter two polynomial families arise in a wide variety of applications, and their short recurrence relations are the basis for a number of efficient algorithms. For historical reasons, algorithm development is more advanced for real orthogonal polynomials. Recent variations of these algorithms tend to be valid only for the Szegö polynomials; they are analogues and not generalizations of the original algorithms.     

Avoiding linear dependencies in LFSR test pattern generators

Linear Feedback Shift Registers (LFSRs) constitute a very efficient mechanism for generating pseudoexhaustive or pseudo-random test sets for the built-in self-testing of digital circuits. However, a well-known problem with the use of LFSRs is the occurrence of linear dependencies in the generated patterns. In this paper, we show for the first time that the amount of linear dependencies can be controlled by selecting appropriate characteristic polynomials and reordering the LFSR cells. We identify two classes of such polynomials which, by appropriate LFSR cell ordering, guarantee that a large ratio of linear dependencies cannot occur. Experimental results show significant enhancements on the fault coverage for pseudo-random testing and support the theoretical relation between minimization of linear dependencies and effective fault coverage.This work was partially supported by NSF grant MIP-9409905, a 1993–94 ACM/IEEE Design Automation Scholarship and a grant from Nissan Corporation. A preliminary version of this work appeared in A Class of Good Characteristic Polynomials for LFSR Test Pattern Generators, in Proc. of IEEE International Conference on Computer Design, Oct. 1994, pp. 292–295, where it received the ICCD'94 Best Paper Award.     

Construction of irreducible polynomials using cubic transformation

The transformationf(x)f(x ³–3x) is studied. We show that for allF _q of characteristic >3 andn1, there existsf(x)F _q [x] of degreen which generates an infinite sequence of irreducible polynomials of degree 3 ⁱ n by the iteration of this transformation.     

基于高维纠缠交换的无酉操作确定性安全量子通信

在分析高维Bell态纠缠交换基本性质的基础上,提出不需要任何酉操作、具有通用性和一般性的高维确定性安全量子通信方案.利用高维Bell测量的结果,发送方和接收方分别进行模加、减运算即可编码、解码信息.构造了两组互补的基,并根据其互补性质,提出了检测高维量子信道是否安全的方法.详细分析了几种常用攻击策略,并计算了这些攻击所引起的错误率,进而推导出通信双方需设定的错误率阈值的上界.     

On the minimum of a positive polynomial over the standard simplex

We present a new positive lower bound for the minimum value taken by a polynomial P$P$ with integer coefficients in k$k$ variables over the standard simplex of R^k${\mathbb{R}}^k$, assuming that P$P$ is positive on the simplex. This bound depends only on the number of variables k$k$, the degree d$d$ and the bitsize τ$\tau$ of the coefficients of P$P$ and improves all the previous bounds for arbitrary polynomials which are positive over the simplex.     

一种高效的QMC检测算法

基于垂直分层空时码的MIMO-OFDM系统提出一种高效的QMC检测算法,该算法对信道矩阵进行一次排序QR分解,对最先检测的信号层采用ML-OSIC算法,用M算法检测中间的信号层,逐层增加保留值M以提高算法有效性,利用串行干扰消除检测余下的信号层。与QRD-M算法相比,QMC检测算法能降低计算复杂度。仿真结果表明,该算法以更低的计算复杂度获得更接近最大似然检测的性能,取得性能与复杂度之间的折中更理想。     

WSN中基于多项式的安全密钥建立方案

针对分层WSN节点的更新,使用二元对称多项式,提出一种安全的建立通信双方会话密钥方案。该方案可保证传输消息的秘密性和完整性,能有效地抵御攻击者对消息的非法篡改、替换和重放。此外,该方案支持通信双方更新会话密钥和增加对节点身份的认证,防止非法节点的欺骗攻击。通过分析可知,该方案和现有方案相比,具有更高的安全性,以及成本和效率的合理性。     

Saturation in multivariate simultaneous approximation

In this paper we present a new result on the saturation of sequences of linear operators in a multivariate and simultaneous setting. Specifically, a small o saturation result is obtained for the partial derivatives of the classical Bernstein bivariate operators on the unit simplex. Solutions of boundary value problems for certain partial differential equations of elliptic type play an important role.     

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.     

Model order reduction methods for coupled systems in the time domain using Laguerre polynomials

In this paper, based on Laguerre polynomials, we present new methods for model reduction of coupled systems in the time domain. By appropriately selected projection matrices, a reduced order system is produced to retain the topology structure of the original system. Meanwhile, it preserves a desired number of Laguerre coefficients of the system’s output, thereby providing good approximation accuracy. We also study the two-sided projection method in the time domain, as well as the stability of reduced order systems. Two numerical examples are used to illustrate the efficiency of the proposed methods.