Using desktop computers to solve large-scale dense linear algebra problems

We provide experimental evidence that current desktop computers feature enough computational power to solve large-scale dense linear algebra problems. While the high computational cost of the numerical methods for solving these problems can be tackled by the multiple cores of current processors, we propose to use the disk to store the large data structures associated with these applications. Our results also show that the limited amount of RAM and the comparatively slow disk of the system pose no problem for the solution of very large dense linear systems and linear least-squares problems. Thus, current desktop computers are revealed as an appealing, cost-effective platform for research groups that have to deal with large dense linear algebra problems but have no direct access to large computing facilities.     

Using two types of computer algebra systems to solve maxwell optics problems

To synthesize Maxwell optics systems, the mathematical apparatus of tensor and vector analysis is generally employed. This mathematical apparatus implies executing a great number of simple stereotyped operations, which are adequately supported by computer algebra systems. In this paper, we distinguish between two stages of working with a mathematical model: model development and model usage. Each of these stages implies its own computer algebra system. As a model problem, we consider the problem of geometrization of Maxwell’s equations. Two computer algebra systems—Cadabra and FORM—are selected for use at different stages of investigation.     

Using quadratic programming to solve high multiplicity scheduling problems on parallel machines

We introduce and analyze several models of schedulingn different types (groups) of jobs onm parallel machines, where in each group all jobs are identical. Our main goal is to exhibit the usefulness of quadratic programming approaches to solve these classes of high multiplicity scheduling problems, with the total weighted completion time as the minimization criterion. We develop polynomial algorithms for some models, and strongly polynomial algorithms for certain special cases. In particular, the model in which the weights are job independent, as well as the generally weighted model in which processing requirements are job independent, can be formulated as an integer convex separable quadratic cost flow problem, and therefore solved in polynomial time. When we specialize further, strongly polynomial bounds are achievable. Specifically, for the weighted model with job-independent processing requirements if we restrict the weights to be machine independent (while still assuming different machine speeds), anO(mn+n logn) algorithm is developed. If it is also assumed that all the machines have the same speed, the complexity of the algorithm can be improved toO(m logm+n logn). These results can be extended to related unweighted models with variable processing requirements in which all the machines are available at time zero. The research of Frieda Granot was partially supported by Natural Sciences and Engineering Research Council of Canada Grant 5-83998. The research of Jadranka Skorin-Kapov was partially supported by National Science Foundation Grant DDM-8909206.     

Stochastic linear quadratic regulation for discrete-time linear systems with input delay

This paper considers the stochastic LQR problem for systems with input delay and stochastic parameter uncertainties in the state and input matrices. The problem is known to be difficult due to the presence of interactions among the delayed input channels and the stochastic parameter uncertainties in the channels. The key to our approach is to convert the LQR control problem into an optimization one in a Hilbert space for an associated backward stochastic model and then obtain the optimal solution to the stochastic LQR problem by exploiting the dynamic programming approach. Our solution is given in terms of two generalized Riccati difference equations (RDEs) of the same dimension as that of the plant.     

邻域内坐标线性变换的光流迭代求解算法

提出邻域内坐标线性变换的光流计算迭代解法。算法允许计算光流的图像间存在一定的灰度偏差,光流计算结果稳定。对于含较大位移的两幅图像,以往方法要用金字塔图像方法计算光流,而该算法则可以一步求解得到图像间最佳整体匹配,比金字塔方法更有优势。算法对图像整体的尺度、平移、旋转或其它线性变换能有效检测。用于人脸图像配准的实验显示,该算法对图像匹配空间搜索有效可行。     

Counterexample-guided abstraction refinement for linear programs with arrays

Predicate abstraction refinement is one of the leading approaches to software verification. The key idea is to abstract the input program into a Boolean Program (i.e. a program whose variables range over the Boolean values only and model the truth values of predicates corresponding to properties of the program state), and refinement searches for new predicates in order to build a new, more refined abstraction. Thus Boolean programs are commonly employed as a simple, yet useful abstraction. However, the effectiveness of predicate abstraction refinement on programs that involve a tight interplay between data-flow and control-flow is still to be ascertained. We present a novel counterexample guided abstraction refinement procedure for Linear Programs with arrays, a fragment of the C programming language where variables and array elements range over a numeric domain and expressions involve linear combinations of variables and array elements. In our procedure the input program is abstracted w.r.t. a family of sets of array indices, the abstraction is a Linear Program (without arrays), and refinement searches for new array indices. We use Linear Programs as the target of the abstraction (instead of Boolean programs) as they allow to express complex correlations between data and control. Thus, unlike the approaches based on predicate abstraction, our approach treats arrays precisely. This is an important feature as arrays are ubiquitous in programming. We provide a precise account of the abstraction, Model Checking, and refinement processes, discuss their implementation in the EUREKA tool, and present a detailed analysis of the experimental results confirming the effectiveness of our approach on a number of programs of interest.     

线性不确定中立型时滞系统的鲁棒二次性能

研究具有非匹配条件的范数有界线性不确定中立型时滞系统的稳定和二次性能控制问题．基于Lyapunov方法，提出了系统鲁棒渐近稳定并满足给定二次性能指标的时滞相关型条件，该条件等价干线性矩阵不等式(LMI)可解性问题，并根据LMI的可行解，构造了状态反馈控制器设计方法．     

引用图片激活扩散的信息加密方法

对于加密编码算法而言,复杂性、非线性和正确性是重要的特性。而人类对知识的处理正好具备这些特性,激活扩散理论则描述了人类对知识的处理方法。受到激活扩散理论的启发,提出一种全新的基于引用图片的信息编码方法。该方法中,每个字符都用一个RGB分量的相对位置和偏移量表示,编码数据则通过激活扩散的方法生成。同一个字符可以用不同的编码表示,而相同的编码也可以表示不同的字符。通过引入激活扩散模型,该方法创建了巨大的搜索空间,从而保证了解码的复杂性;另一方面,该方法也减少了密文和明文间的相关性。     

Algorithms to solve some problems of concave programming with linear constraints

Consideration was given to the separable problem of concave programming with linear constraints for which two groups of new algorithms relying on a unique theoretical basis were proposed. The first group of (precise) algorithms approximates the optimal value of a functional from below, the second group of (mostly approximate) algorithms, does this from above.     

Explicit cost sensitivity analysis for linear systems with quadratic criteria

For linear systems subject to large variations in a single parameter, it is shown that the quadratic cost can be expressed exactly as the ratio of two polynomials in that parameter.     

Using an interval graph approach to efficiently solve the housing benefit data retrieval problem

Rappos and Thompson use a set covering formulation and a commercial software package to solve the problem of trying to minimize the number of data sets that have to be read in retrieving all new housing benefit (HB) data entries for a fixed period of time. In this paper, we show that determining the minimum number of data sets that have to be read in retrieving all new HB data entries for a fixed period of time can be solved by finding a minimum size clique cover for an interval graph. Since it is well‐known that a greedy algorithm finds a guaranteed minimum size clique cover for an interval graph, this approach will be more efficient than a set covering approach. Finally, it is obvious that this interval graph formulation and greedy algorithm solution approach is applicable to other data retrieval problems.     

Application of quadratic differential forms to designing linear controllers for nonlinearities

We consider the following problem: given a nonlinear system (possibly with memory), parametrize a class of linear systems that can be interconnected (through fairly general interconnection constraints) with the nonlinear system to yield a stable autonomous system. We address this problem in a behavioral theoretic setting by constructing Quadratic Differential Forms (QDFs) called storage functions associated with the linear system. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Linear quadratic regulation for linear time-varying systems with multiple input delays

This paper studies the classic linear quadratic regulation (LQR) problem for both continuous-time and discrete-time systems with multiple input delays. For discrete-time systems, the LQR problem for systems with single input delay has been studied in existing literature, whereas a solution to the multiple input delay case is not known to our knowledge. For continuous-time systems with multiple input delays, the LQR problem has been tackled via an infinite dimensional system theory approach and a frequency/time domain approach. The objective of the present paper is to give an explicit solution to the LQR problem via a simple and intuitive approach. The main contributions of the paper include a fundamental result of duality between the LQR problem for systems with multiple input delays and a smoothing problem for an associated backward stochastic system. The duality allows us to obtain a solution to the LQR problem via standard projection in linear space. The LQR controller is simply constructed by the solution of one backward Riccati difference (for the discrete-time case) or differential (for the continuous-time case) equation of the same order as the plant (ignoring the delays).     

Cooperative linear quadratic differential games for uncertain systems with conservative players

This paper investigates cooperative linear quadratic differential games for uncertain dynamic systems with conservative players, who attempt to optimize the worst-case outcomes with limited a priori knowledge about the uncertainties. Without properly designed control strategies, the uncertainties could cause significant impacts on the performance indexes of players and spoil the cooperation among players. In this paper, compensation-based robust control techniques are applied to handle the uncertainties, including parameter perturbations and external disturbances, by transforming the impacts of the uncertainties into a more tractable form. Subsequently, using Vickrey–Clarke–Groves principles, an auction-based control allocation mechanism is designed to incentivize the players to cooperatively implement the compensation. With the methods proposed, the worst-case performance indexes of players can be improved, and the cooperation among players is maintained in the uncertain system. Numerical examples demonstrate the effectiveness of the proposed methods.