Computation of lucid factors for Bezout identity

One approach to control system design is based on the Youla parameterization, and the application of this design approach requires one to solve for system coprime factors and the solution to the Bezout identity. A new and simple computational approach to acquire sets of factors that satisfy Bezout identity is developed; the algorithm along with the associated software in the MATLAB environment are presented. Previous work, required the solution to two pole-placement problems along with implementation of the Leverrier algorithm for inversion of four alphanumeric matrices. The presented software is by far less computationally intensive, and it only requires solution to a set of simultaneous linear algebraic equations.     

Symbolic and Numeric Methods for Exploiting Structure in Constructing Resultant Matrices

Resultants characterize the existence of roots of systems of multivariate nonlinear polynomial equations, while their matrices reduce the computation of all common zeros to a problem in linear algebra. Sparse elimination theory has introduced the sparse (or toric) resultant, which takes into account the sparse structure of the polynomials. The construction of sparse resultant, or Newton, matrices is the critical step in the computation of the multivariate resultant and the solution of a nonlinear system. We reveal and exploit the quasi-Toeplitz structure of the Newton matrix, thus decreasing the time complexity of constructing such matrices by roughly one order of magnitude to achieve quasi-quadratic complexity in the matrix dimension. The space complexity is also decreased analogously. These results imply similar improvements in the complexity of computing the resultant polynomial itself and of solving zero-dimensional systems. Our approach relies on fast vector-by-matrix multiplication and uses the following two methods as building blocks. First, a fast and numerically stable method for determining the rank of rectangular matrices, which works exclusively over floating point arithmetic. Second, exact polynomial arithmetic algorithms that improve upon the complexity of polynomial multiplication under our model of sparseness, offering bounds linear in the number of variables and the number of non-zero terms.     

On the Computation of Elementary Divisors of Integer Matrices

We describe a “semi-modular" algorithm which computes for a given integer matrix A of known rank and a given prime p the multiplicities of p in the factorizations of the elementary divisors ofA . Here “semi-modular" means that we apply operations to the integer matrix A but the operations are driven by considering only reductions of row vectors modulo p.     

Parallel Computation of High-Dimensional Robust Correlation and Covariance Matrices

The computation of covariance and correlation matrices are critical to many data mining applications and processes. Unfortunately the classical covariance and correlation matrices are very sensitive to outliers. Robust methods, such as Quadrant Correlation (QC) and the Maronna method, have been proposed. However, existing algorithms for QC only give acceptable performance when the dimensionality of the matrix is in the hundreds; and the Maronna method is rarely used in practice because of its high computational cost. In this paper we develop parallel algorithms for both QC and the Maronna method. We evaluate these parallel algorithms using a real data set of the gene expression of over 6000 genes, giving rise to a matrix of over 18 million entries. In our experimental evaluation, we explore scalability in dimensionality and in the number of processors, and the trade-offs between accuracy and computational efficiency. We also compare the parallel behaviours of the two methods. From a statistical standpoint, the Maronna method is more robust than QC. From a computational standpoint, while QC requires less computation, interestingly the Maronna method is much more parallelizable than QC. After a thorough experimentation, we conclude that for many data mining applications, both QC and Maronna are viable options. Less robust, but faster, QC is the recommended choice for small parallel platforms. On the other hand, the Maronna method is the recommended choice when a high degree of robustness is required, or when the parallel platform features a large number of processors (e.g., 32).     

Fast Recursive Computation of Krawtchouk Polynomials

Krawtchouk polynomials (KPs) and their moments are used widely in the field of signal processing for their superior discriminatory properties. This study proposes a new fast recursive algorithm to compute Krawtchouk polynomial coefficients (KPCs). This algorithm is based on the symmetry property of KPCs along the primary and secondary diagonals of the polynomial array. The \(n-x\) plane of the KP array is partitioned into four triangles, which are symmetrical across the primary and secondary diagonals. The proposed algorithm computes the KPCs for only one triangle (partition), while the coefficients of the other three triangles (partitions) can be computed using the derived symmetry properties of the KP. Therefore, only N / 4 recursion times are required. The proposed algorithm can also be used to compute polynomial coefficients for different values of the parameter p in interval (0, 1). The performance of the proposed algorithm is compared with that in previous literature in terms of image reconstruction error, polynomial size, and computation cost. Moreover, the proposed algorithm is applied in a face recognition system to determine the impact of parameter p on feature extraction ability. Simulation results show that the proposed algorithm has a remarkable advantage over other existing algorithms for a wide range of parameters p and polynomial size N, especially in reducing the computation time and the number of operations utilized.     

Verified Computation of Fast Decreasing Polynomials

In this paper the problem of verified numerical computation of algebraic fast decreasing polynomials approximating the Dirac delta function is considered. We find the smallest degree of the polynomials and give precise estimates for this degree. It is shown that the computer algebra system Maple does not always graph such polynomials reliably because of evaluating the expressions in usual floating-point arithmetic. We propose a procedure for verified computation of the polynomials and use it to produce their correct graphic presentation in Maple.     

Fast Computation of Optimal Contact Forces

We consider the problem of computing the smallest contact forces, with point-contact friction model, that can hold an object in equilibrium against a known external applied force and torque. It is known that the force optimization problem (FOP) can be formulated as a semidefinite programming problem (SDP) or a second-order cone problem (SOCP), and thus, can be solved using several standard algorithms for these problem classes. In this paper, we describe a custom interior-point algorithm for solving the FOP that exploits the specific structure of the problem, and is much faster than these standard methods. Our method has a complexity that is linear in the number of contact forces, whereas methods based on generic SDP or SOCP algorithms have complexity that is cubic in the number of forces. Our method is also much faster for smaller problems. We derive a compact dual problem for the FOP, which allows us to rapidly compute lower bounds on the minimum contact force and certify the infeasibility of a FOP. We use this dual problem to terminate our optimization method with a guaranteed accuracy. Finally, we consider the problem of solving a family of FOPs that are related. This occurs, for example, in determining whether force closure occurs, in analyzing the worst case contact force required over a set of external forces and torques, and in the problem of choosing contact points on an object so as to minimize the required contact force. Using dual bounds, and a warm-start version of our FOP method, we show how such families of FOPs can be solved very efficiently.     

机器人动力学的快速实时计算

本文给出了一种相对于机器人各臂坐标系,计算 Lagrange-Euler 形式的机器人动力学方程快速实时方法。在计算上,这种新方法比文献〔1〕～〔3〕中的方法更有效,计算量更小。对于一个六自由度的机器人,它的计算量至多为893个乘法与719个加法。尽管在理论上这种方法的计算量比 Newton-Euler 方法的计算量(852个乘法与738个加法)约多40个乘法,伹实际程序运行时间比 Newton-Euler 方法短。     

新的图像几何矩快速算法

矩技术作为一种有效的图像描述方法,在图像分析方面有着重要应用,但由于涉及大量计算,在一定程度上制约其应用.提出一种新的基于GPU的快速计算方法,它首先将图像加戟成纹理,然后在像素着色器中利用GPU内核同时对多个像素进行处理,快速计算所需矩值.实验结果表明,与当前的直接法和对称核快速算法相比,文中提出的算法可有效节省计算时间,尤其在图像尺寸较大及所使用的矩的阶数较高的情况下,计算性能更优.     

应用FFT进行超长数字乘法的快速计算

通过研究超长数字的表示方法和FFT算法的改进,实现了超长数字乘法的快速计算,并给出了关键部分的算法,分析了算法的效率,为相关应用提供了一个借鉴.     

应用FFT进行超长数字乘法的快速计算

通过研究超长数字的表示方法和FFT算法的改进，实现了超长数字乘法的快速计算，并给出了关键部分的算法，分析了算法的效率，为相关应用提供了一个借鉴。     

Computation of Determinants, Adjoint Matrices, and Characteristic Polynomials without Division

Algorithms are proposed for computing the characteristic polynomial, determinant, and adjoint matrix for a n × n matrix and for solving a system of n-1 linear homogeneous equations in n variables by Cramer's rule using O(n ⁴ ) ring operations (without the division operation) over an arbitrary commutative ring. The exponent in the estimate of the computation time can be additionally reduced if an algorithm of asymptotically fast matrix multiplication is used.     

Triangle Influence Supersets for Fast Distance Computation

We present an acceleration structure to efficiently query the Signed Distance Field (SDF) of volumes represented by triangle meshes. The method is based on a discretization of space. In each node, we store the triangles defining the SDF behaviour in that region. Consequently, we reduce the cost of the nearest triangle search, prioritizing query performance, while avoiding approximations of the field. We propose a method to conservatively compute the set of triangles influencing each node. Given a node, each triangle defines a region of space such that all points inside it are closer to a point in the node than the triangle is. This property is used to build the SDF acceleration structure. We do not need to explicitly compute these regions, which is crucial to the performance of our approach. We prove the correctness of the proposed method and compare it to similar approaches, confirming that our method produces faster query times than other exact methods.     

基于子空间聚类的快速高斯计算

针对嵌入式语音识别系统,实现了基于子空间聚类的快速高斯计算,简化了HMM模型的计算复杂度,回避了声学模型重新训练的问题。在嵌入式系统上的实验数据表明,识别速度能获得20%以上的提高,而且识别率没有大幅降低。     

A Fast Algorithm for Inverse Colormap Computation

The inverse colormap operation is the process which allows an image to be displayed with a limited set of colors. In order to obtain a minimal visual distortion between the input image annd the one displayed, inverse colormap algorithms associate each color with its nearest representative. The method presented in this paper is carried out in two steps. First, the 3D Voronoi diagram implicitly used by inverse colormap algorithms is approximated using a Karhunen-Loève transformation. Then, a correcting step is carried out in order to reduce the in uence of the first approximation. The complexity of our algorithm is independent of the size of the colormap. Moreover, its results are equal or quite close to the optimal solution.     

模n的大整数幂乘的一种快速算法

在RSA公钥密码体制中，要提高模n的大整数幂乘的运算效率，主要是解决两个方面的问题：（1）大整数的算术运算，特别是大整数的乘除法；（2）降低幂模运算的实际次数。文章从这两个方面进行研究，实现了大整数幂乘的一种快速计算。并给出了关键部分的算法，分析了算法的效率。     

模n的大整数幂乘的一种快速算法

在RSA公钥密码体制中,要提高模n的大整数幂乘的运算效率,主要是解决两个方面的问题:⑴大整数的算术运算,特别是大整数的乘除法;⑵降低幂模运算的实际次数。文章从这两个方面进行研究,实现了大整数幂乘的一种快速计算,并给出了关键部分的算法,分析了算法的效率。     

一种计算机平滑曲线的画法和快速算法

本文详细阐述了一种在计算机上通过消除锯齿感绘制平滑曲线的原理，给出了这种方法的计算机快速算法，并将该算法与其它曲线绘制算法进行了性能比较。     

基于流水光总线阵列的快速矩阵乘法运算

基于流水光总线的可重构线性阵列系统(LARPBS)是一种建立在光总线上的并行计算模型,许多研究工作者已经在该模型上设计出了一些高效的并行算法。该文主要介绍了LARPBS模型及其快速矩阵乘法运算,从而使人们更加了解光总线计算模型及其优越性,为今后进一步研究光总线模型及其并行算法奠定了基础。