A new version of Kovarik’s approximate orthogonalization algorithm without matrix inversion

In 1970 Kovarik proposed approximate orthogonalization algorithms. One of them (algorithm B) has quadratic convergence but requires at each iteration the inversion of a matrix of similar dimension to the initial one. An attempt to overcome this difficulty was made by replacing the inverse with a finite Neumann series expansion involving the original matrix and its adjoint. Unfortunately, this new algorithm loses the quadratic convergence and requires a large number of terms in the Neumann series which results in a dramatic increase in the computational effort per iteration. In this paper we propose a much simpler algorithm which, by using only the first two terms in a different series expansion, gives us the desired result with linear convergence. Systematic numerical experiments for collocation and Toeplitz matrices are also described.     

Solution of progressively changing equilibrium equations for nonlinear structures

In the analysis of nonlinear structures by tangent stiffness methods, the equilibrium equations change progressively during the analysis. When direct methods of solving these equations are used, it may be possible to re-use a substantial part of the previously reduced coefficient matrix, and hence substantially reduce the equation solving effort. This paper examines procedures for re-solving equations when only selected parts of the reduced matrix need to be modified.The Crout and Cholesky algorithms are first reviewed for initial complete reduction and subsequent selective reduction of the coefficient matrix, and it is shown that the Cholesky algorithm is superior for selective reduction. A general procedure is then presented for identifying those parts of the coefficient matrix which remain unchanged as the structure changes. Finally, a general purpose in-core equation solver is presented, in which those parts of the previously reduced matrix which need to be modified are determined automatically during the solution process, and only these portions are changed. The equation solver is based on the Cholesky algorithm, and is applicable to both positive-definite and well conditioned non-positive-definite symmetrical systems of equations.     

MIMO-OFDM系统基于QR分解的信号检测算法

论文研究了MIMO-OFDM系统基于QR分解的几种信号检测算法,分析了各种算法的优缺点;指出信号检测顺序是降低误差传播概率的关键。针对VBLAST算法计算量大的缺点,提出采用SQRD算法,该算法利用迭代运算代替矩阵求逆运算,降低了VBLAST算法的计算量,并采用MMSE准则对该算法进行进一步推广。仿真结果表明采用MMSE-SQRD算法优于除ML算法以外的检测算法;在NT=NR=4时,结果表明在SER为10-3时MMSE-SQRD算法优于MMSE-BLAST算法2dB。     

Analytical expressions of sensitivities for shape variables in linear bending systems

Sensitivity analysis is a very interesting field in structural engineering because of its variety of uses. But the computational effort to obtain the analytical values of such sensitivities is a tough task that has been generally avoided when considering flexural systems. Instead some numerical approaches have been used to solve the problem. However, carrying out the sensitivity analysis by this method leads to considerable errors, especially with shape variables as many authors have pointed out. In this paper analytical expressions of sensitivities analysis with respect to shape variables are carried out for bending systems in linear theory. The development presented in this paper starts evaluating the sensitivity analysis of the nodal movements performing the loading vector and stiffness matrix sensitivity analysis. Then this research evaluates the sensitivity analysis of the maximum normal stresses. Finally, some structural examples where the previous analytical sensitivities are evaluated are exposed relating the results versus the corresponding results obtained by finite difference methods and some conclusions are drawn from the work presented.     

Spectral algorithms for supervised learning

We discuss how a large class of regularization methods, collectively known as spectral regularization and originally designed for solving ill-posed inverse problems, gives rise to regularized learning algorithms. All of these algorithms are consistent kernel methods that can be easily implemented. The intuition behind their derivation is that the same principle allowing for the numerical stabilization of a matrix inversion problem is crucial to avoid overfitting. The various methods have a common derivation but different computational and theoretical properties. We describe examples of such algorithms, analyze their classification performance on several data sets and discuss their applicability to real-world problems.     

Structural reanalysis for topological modifications – a unified approach

A unified approach for structural reanalysis of all types of topological modifications is presented. The modifications considered include various cases of deletion and addition of members and joints. The most challenging problem where the structural model is itself allowed to vary is presented. The two cases, where the number of degrees of freedom is decreased and increased, are considered. Various types of modified topologies are discussed, including the common conditionally unstable structures. The solution procedure is based on the combined approximations approach and involves small computational effort. Numerical examples show that accurate results are achieved for significant topological modifications. Exact solutions are obtained efficiently for modifications in a small number of members. Received April 4, 2000     

Graph theoretic foundations of multibody dynamics

This second part of a two part paper uses concepts from graph theory to obtain a deeper understanding of the mathematical foundations of multibody dynamics. The first part (Jain in Graph theoretic foundations of multibody dynamics. Part I. Structural properties, 2010) established the block-weighted adjacency (BWA) matrix structure of spatial operators associated with serial- and tree-topology multibody system dynamics, and introduced the notions of spatial kernel operators (SKO) and spatial propagation operators (SPO). This paper builds upon these connections to show that key analytical results and computational algorithms are a direct consequence of these structural properties and require minimal assumptions about the specific nature of the underlying multibody system. We formalize this notion by introducing the notion of SKO models for general tree-topology multibody systems. We show that key analytical results, including mass-matrix factorization, inversion, and decomposition hold for all SKO models. It is also shown that key low-order scatter/gather recursive computational algorithms follow directly from these abstract-level analytical results. Application examples to illustrate the concrete application of these general results are provided. The paper also describes a general recipe for developing SKO models. The abstract nature of SKO models allows for the application of these techniques to a very broad class of multibody systems.     

区间模糊谱聚类图像分割方法

近年来谱聚类算法在模式识别和计算机视觉领域被广泛应用,而相似性矩阵的构造是谱聚类算法的关键步骤。针对传统谱聚类算法计算复杂度高难以应用到大规模图像分割处理的问题,提出了区间模糊谱聚类图像分割方法。该方法首先利用灰度直方图和区间模糊理论得到图像灰度间的区间模糊隶属度,然后利用该隶属度构造基于灰度的区间模糊相似性测度,最后利用该相似性测度构造相似性矩阵并通过规范切图谱划分准则对图像进行划分,得到最终的图像分割结果。由于区间模糊理论的引入,提高了传统谱聚类的分割性能,对比实验也表明该方法在分割效果和计算复杂度上都有较大的改善。     

Pattern search algorithms for nonlinear inversion of high-frequency Rayleigh-wave dispersion curves

Inversion of Rayleigh wave dispersion curves is challenging for most local-search methods due to its high nonlinearity and to its multimodality. In this paper, we implemented and tested a Rayleigh wave dispersion curve inversion scheme based on GPS Positive Basis 2N, a commonly used pattern search algorithm. Incorporating complete poll and complete search strategies based on GPS Positive Basis 2N into the inverse procedure greatly enhances the performance of pattern search algorithms because the two steps can effectively locate the promising areas in the solution space containing the global minima and significantly reduce the computation cost, respectively.The proposed inverse procedure was applied to nonlinear inversion of fundamental-mode Rayleigh wave dispersion curves for a near-surface shear (S)-wave velocity profile. The calculation efficiency and stability of the inversion scheme are tested on three synthetic models and a real example from a roadbed survey in Henan, China. Effects of the number of data points, the reduction of the frequency range of the considered dispersion curve, errors in P-wave velocities and density, the initial S-wave velocity profile as well as the number of layers and their thicknesses on inversion results are also investigated in the present study to further evaluate the performance of the proposed approach.Results demonstrate that pattern search algorithms applied to nonlinear inversion of high-frequency surface wave data should be considered good not only in terms of accuracy but also in terms of the computation effort due to their global and deterministic search process.     

Complexity of parallel matrix computations

We estimate parallel complexity of several matrix computations under both Boolean and arithmetic machine models using deterministic and probabilistic approaches. Those computations include the evaluation of the inverse, the determinant, and the characteristic polynomial of a matrix. Recently, processor efficiency of the previous parallel algorithms for numerical matrix inversion has been substantially improved in (Pan and Reif, 1987), reaching optimum estimates up to within a logarithmic factor; that work, however, applies neither to the evaluation of the determinant and the characteristic polynomial nor to exact matrix inversion nor to the numerical inversion of ill-conditioned matrices. We present four new approaches to the solution of those latter problems (having several applications to combinatorial computations) in order to extend the suboptimum time and processor bounds of (Pan and Reif, 1987) to the case of computing the inverse, determinant, and characteristic polynomial of an arbitrary integer input matrix. In addition, processor efficient algorithms using polylogarithmic parallel time are devised for some other matrix computations, such as triangular and QR-factorizations of a matrix and its reduction to Hessenberg form.     

Structural optimization under uncertain loads and nodal locations

This paper presents algorithms for solving structural topology optimization problems with uncertainty in the magnitude and location of the applied loads and with small uncertainty in the location of the structural nodes. The second type of uncertainty would typically arise from fabrication errors where the tolerances for the node locations are small in relation to the length scale of the structural elements. We first review the discrete form of the uncertain loads problem, which has been previously solved using a weighted average of multiple load patterns. With minor modifications, we extend this solution to include loads described by continuous joint probability density functions. We then proceed to the main contribution of this paper: structural optimization under uncertainty in the nodal locations. This optimization problem is computationally difficult because it involves variations of the inverse of the structural stiffness matrix. It is shown, however, that for small uncertainties the problem can be recast into a simpler but equivalent structural optimization problem with equivalent uncertain loads. By expressing these equivalent loads in terms of continuous random variables, we are able to make use of the extended form of the uncertain loads problem presented in the first part of this paper. The optimization algorithms are developed in the context of minimum compliance (maximum stiffness) design. Simple examples are presented. The results demonstrate that load and nodal uncertainties can have dramatic impact on optimal design. For structures containing thin substructures under axial loads, it is shown that these uncertainties (a) are of first-order significance, influencing the linear elastic response quantities, and (b) can affect designs by avoiding unrealistically optimistic and potentially unstable structures. The additional computational cost associated with the uncertainties scales linearly with the number of uncertainties and is insignificant compared to the cost associated with solving the deterministic structural optimization problem.     

Fast modified global k-means algorithm for incremental cluster construction

The k-means algorithm and its variations are known to be fast clustering algorithms. However, they are sensitive to the choice of starting points and are inefficient for solving clustering problems in large datasets. Recently, incremental approaches have been developed to resolve difficulties with the choice of starting points. The global k-means and the modified global k-means algorithms are based on such an approach. They iteratively add one cluster center at a time. Numerical experiments show that these algorithms considerably improve the k-means algorithm. However, they require storing the whole affinity matrix or computing this matrix at each iteration. This makes both algorithms time consuming and memory demanding for clustering even moderately large datasets. In this paper, a new version of the modified global k-means algorithm is proposed. We introduce an auxiliary cluster function to generate a set of starting points lying in different parts of the dataset. We exploit information gathered in previous iterations of the incremental algorithm to eliminate the need of computing or storing the whole affinity matrix and thereby to reduce computational effort and memory usage. Results of numerical experiments on six standard datasets demonstrate that the new algorithm is more efficient than the global and the modified global k-means algorithms.     

Comments on "Linear function observer for linear discrete-time systems"

Two alternative systematic algorithms are suggested to compute the matrixTnecessary to design a minimum-time linear function observer. The simplicity of these algorithms gives mole insight to the understanding of the observer structure. Furthermore, the computational effort required to obtain the matrixJis spared.     

Linear response algorithms for approximate inference in graphical models

Belief propagation (BP) on cyclic graphs is an efficient algorithm for computing approximate marginal probability distributions over single nodes and neighboring nodes in the graph. However, it does not prescribe a way to compute joint distributions over pairs of distant nodes in the graph. In this article, we propose two new algorithms for approximating these pairwise probabilities, based on the linear response theorem. The first is a propagation algorithm that is shown to converge if BP converges to a stable fixed point. The second algorithm is based on matrix inversion. Applying these ideas to gaussian random fields, we derive a propagation algorithm for computing the inverse of a matrix.     

A parallel approach of the inverse kinematics solutions for robots using a transputer network

This article presents a parallel method for computing inverse kinematics solutions for robots with closed-form solutions moving along a straight line trajectory specified in Cartesian space. Zhang and Paul's approach¹ is improved for accuracy and speed. Instead of using previous joint positions as proposed by Zhang and Paul, a first order prediction strategy is used to decouple the dependency between joint positions, and a zero order approximation solution is computed. A compensation scheme using Taylor series expansion is applied to obtain the trajectory gradient in joint space to replace the correction scheme proposed by Zhang and Paul. The configuration of a Mitsubishi RV-M1 robot is used for the simulation of a closed-form inverse kinematics solutions. An Alta SuperLink/XL with four transputer nodes is used for parallel implementation. The simulation results show a significant improvement in displacement tracking errors and joint configuration errors along the straight line trajectory. The computational latency is reduced as well. The modified approach proposed in this work is more accurate and faster than Zhang and Paul's approach for robots with closed-form inverse kinematics solutions. © 1996 John Wiley & Sons, Inc.     

Computing Exact Bounds on Elements of an Inverse Interval Matrix is NP-Hard

For a given interval matrix, it would be valuable to have a practical method for determining the family of matrices which are inverses of its members. Since the exact family of inverse matrices can be difficult to find or to describe, effort is often applied to developing methods for determining matrix families with interval structure which "best" approximate or contain it. A common approach is to seek exact bounds on individual elements. In this paper, we show that computing exact bounds is NP-hard; therefore any algorithm will have at least exponential-time worst-case computational cost unless P = NP.     

基于基因表达式编程的TSP问题求解

利用遗传算法求解组合优化问题时,需要特有的遗传算子,才能在候选解空间中有效搜索和进化。基因表达式编程（GEP）是进化计算家族的新成员。旅游商问题（TSP）是典型的组合优化问题,得到了广泛的研究,它的研究成果将对求解NP类问题产生重要影响。基于基因表达式编程（GEP）来解决TSP问题,引入适用组合优化的遗传算子：逆串,基因串的删/插等,最后进行了实验,展示GEP解决TSP问题的方法。实验表明GEP能有效解决TSP问题,设计的系统是强壮健康,其求解速度快且解的质量好。     

The approximate reanalysis method for topology optimization under harmonic force excitations with multiple frequencies

In mode acceleration method for topology optimization related harmonic response with multiple frequencies, most of the computation effort is invested in the solution of the eigen-problem. This paper is focused on reduction of the computational effort in repeated solution of the eigen-problem involved in mode acceleration method. The block combined approximation with shifting method is adopted for eigen-problem reanalysis, which simultaneously calculates some eigenpairs of modified structures. The triangular factorizations of shifted stiffness matrices generated within a certain number of design iterations are utilized to calculate the modes. For improving computational efficiency, Basic Linear Algebra Subprograms (BLAS) are utilized. The reanalysis method is based on matrix-matrix operations with Level-3 BLAS and can provide very fast development of approximate solutions of high quality for frequencies and associated mode shapes of the modified structure. Numerical examples are given to demonstrate the efficiency of the proposed topology optimization procedure and the accuracy of the approximate solutions.     

Sensitivity analysis of optimum solutions by updating active constraints: application in aircraft structural design

Often the parameters considered as constants in an optimization problem have some uncertainty and it is interesting to know how the optimum solution is modified when these values are changed. The only way to continue having the optimal solution is to perform a new optimization loop, but this may require a high computational effort if the optimization problem is large. However, there are several procedures to obtain the new optimal design, based on getting the sensitivities of design variables and objective function with respect to a fixed parameter. Most of these methods require obtaining second derivatives which has a significant computational cost. This paper uses the feasible direction-based technique updating the active constraints to obtain the approximate optimum design. This procedure only requires the first derivatives and it is noted that the updating set of active constraints improves the result, making possible a greater fixed parameter variation. This methodology is applied to an example of very common structural optimization problems in technical literature and to a real aircraft structure.