Entrywise perturbation theory and error analysis for Markov chains

Summary Grassmann, Taksar, and Heyman introduced a variant of Gaussian climination for computing the steady-state vector of a Markov chain. In this paper we prove that their algorithm is stable, and that the problem itself is well-conditioned, in the sense of entrywise relative error. Thus the algorithm computes each entry of the steady-state vector with low relative error. Even the small steady-state probabilities are computed accurately. The key to our analysis is to focus on entrywise relative error in both the data and the computed solution, rather than making the standard assessments of error based on norms. Our conclusions do not depend on any Condition numbers for the problem.This work was supported by NSF under grants DMS-9106207 and DDM-9203134     

论强单调算子下的邻点算法

考虑强单调算子下的邻点算法.证明了它容许弱于可和性条件的绝对误差以及每个松弛因子不超过某个较小正数的相对误差.     

Error analysis for matrix eigenvalue algorithm based on the discrete hungry Toda equation

Based on the integrable discrete hungry Toda (dhToda) equation, the authors designed an algorithm for computing eigenvalues of a class of totally nonnegative matrices (Ann Mat Pura Appl, doi:10.1007/s10231-011-0231-0). This is named the dhToda algorithm, and can be regarded as an extension of the well-known qd algorithm. The shifted dhToda algorithm has been also designed by introducing the origin shift in order to accelerate the convergence. In this paper, we first propose the differential form of the shifted dhToda algorithm, by referring to that of the qds (dqds) algorithm. The number of subtractions is then reduced and the effect of cancellation in floating point arithmetic is minimized. Next, from the viewpoint of mixed error analysis, we investigate numerical stability of the proposed algorithm in floating point arithmetic. Based on this result, we give a relative perturbation bound for eigenvalues computed by the new algorithm. Thus it is verified that the eigenvalues computed by the proposed algorithm have high relative accuracy. Numerical examples agree with our error analysis for the algorithm.     

An effective PSO-inspired algorithm for the team orienteering problem

The Team Orienteering Problem (TOP) is a particular vehicle routing problem in which the aim is to maximize the profit gained from visiting customers without exceeding a travel cost/time limit. This paper proposes a new and fast evaluation process for TOP based on an interval graph model and a Particle Swarm Optimization inspired Algorithm (PSOiA) to solve the problem. Experiments conducted on the standard benchmark of TOP clearly show that our algorithm outperforms the existing solving methods. PSOiA reached a relative error of 0.0005% whereas the best known relative error in the literature is 0.0394%. Our algorithm detects all but one of the best known solutions. Moreover, a strict improvement was found for one instance of the benchmark and a new set of larger instances was introduced.     

处理噪声问题的泰勒展开交替最小化算法

为了处理图像、计算机视觉和生物信息等领域中广泛存在的稀疏大噪声和高斯噪声问题,提出了一种利用交替方向最小化思想求解主成分追求松弛模型的泰勒展开交替最小化算法(TEAM).采用推广泰勒展开和收缩算子等技术推导出低秩矩阵和稀疏大噪声矩阵的迭代方向矩阵,加入连续技术提高算法的收敛速率,设计出TEAM算法的求解步骤.实验中,将TEAM算法与该领域的顶级算法作分析对比.结果表明,TEAM算法时间优势明显,误差优势略好.     

An asymptotically exact algorithm for the maximum traveling salesman problem in a finite-dimensional normed space

We consider the geometric maximum traveling salesman problem on assuming that the vertices of a graph lie in an arbitrary finite-dimensional normed space. For this problem we obtain an approximate algorithm with the relative error tending to zero as the number of vertices grows. The algorithm generalizes Serdyukov’s algorithm for the Euclidean Max TSP.     

Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP

We consider greedy algorithms that allow partial regret. As an example we consider a variant of the cheapest insertion algorithm for the TSP. Our numerical study indicates that in most cases it significantly reduces the relative error, and the added computational time is quite small.     

A modification of Hochbaum and Shmoys' algorithm for scheduling problems

The dual approximation algorithm of Hochbaum and Shmoys for solving the minimum makespan problem on a set of identical machines is modified in such a way that it turns into an optimal algorithm when the relative error is chosen properly.     

基于时域误差限的大规模系统自适应模型降阶

为满足解大规模动态系统常微分方程组对精度和速度权衡的要求,提出了一种基于误差限的大规模系统自适应模型降阶方法,其中方法的误差分析基于时域最大误差限,降阶方法基于SVD-Krylov子空间的方法.方法既考虑了算法的复杂性,又保证了算法的精度.通过对典型实例分析,结果表明该方法在给定相对误差限10~(-4)下得出的降阶阶数在不同频率下都能给出很好的近似精度,低频1~10Hz平均相对误差为1.1812×10~(-5),高频1~10GHz平均相对误差为5.6408×10~(-5),即在很宽的频率范围内都能满足精度要求.     

An Application of the Bin-packing Technique to Job Scheduling on Uniform Processors

A non-polynomial algorithm is presented for solving the minimum makespan problem on a set of uniform machines. This algorithm uses the bin-packing technique and provides an approximate solution which turns into an optimal one when the relative error is chosen small enough.     

Relative error propagation in the recursive solution of linear recurrence relations

This paper is concerned with the numerical solution of the general initial value problem for linear recurrence relations. An error analysis of direct recursion is given, based on relative rather than absolute error, and a theory of relative stability developed.Miller's algorithm for second order homogeneous relations is extended to more general cases, and the propagation of errors analysed in a similar manner. The practical significance of the theoretical results is indicated by applying them to particular classes of problem.     

A practical relative error criterion for augmented Lagrangians

This paper develops a new error criterion for the approximate minimization of augmented Lagrangian subproblems. This criterion is practical since it is readily testable given only a gradient (or subgradient) of the augmented Lagrangian. It is also “relative” in the sense of relative error criteria for proximal point algorithms: in particular, it uses a single relative tolerance parameter, rather than a summable parameter sequence. Our analysis first describes an abstract version of the criterion within Rockafellar’s general parametric convex duality framework, and proves a global convergence result for the resulting algorithm. Specializing this algorithm to a standard formulation of convex programming produces a version of the classical augmented Lagrangian method with a novel inexact solution condition for the subproblems. Finally, we present computational results drawn from the CUTE test set—including many nonconvex problems—indicating that the approach works well in practice.     

COMPUTING TRACE OF FUNCTION OF MATRIX

1 IntroductionIn some applications such as computational phySics, one often computes det~inant Ofmatrix and trace Of function of matrix. For ~ fun~ such as f(x) ~1/x or f(x) In (x) computing tr(f(A) ),i. e. tr(A--' ) or In(det(A) ) respeCtively, may be highly sensitiveproblems. When the matrix she n is small, we can compute these problemS explicits by usaldense ~x computation methods L6J. General speaking, such methods require O(n3) floating point OPerations. However, when n atomes larg…     

Importance Sampling Simulations of Markovian Reliability Systems Using Cross-Entropy

This paper reports simulation experiments, applying the cross entropy method such as the importance sampling algorithm for efficient estimation of rare event probabilities in Markovian reliability systems. The method is compared to various failure biasing schemes that have been proved to give estimators with bounded relative errors. The results from the experiments indicate a considerable improvement of the performance of the importance sampling estimators, where performance is measured by the relative error of the estimate, by the relative error of the estimator, and by the gain of the importance sampling simulation to the normal simulation.     

Computing singular values of diagonally dominant matrices to high relative accuracy

For a (row) diagonally dominant matrix, if all of its off-diagonal entries and its diagonally dominant parts (which are defined for each row as the absolute value of the diagonal entry subtracted by the sum of the absolute values of off-diagonal entries in that row) are accurately known, we develop an algorithm that computes all the singular values, including zero ones if any, with relative errors in the order of the machine precision. When the matrix is also symmetric with positive diagonals (i.e. a symmetric positive semi-definite diagonally dominant matrix), our algorithm computes all eigenvalues to high relative accuracy. Rounding error analysis will be given and numerical examples will be presented to demonstrate the high relative accuracy of the algorithm.

     

Computing the Expected Markov Reward Rates with Stationarity Detection and Relative Error Control

By combining in a novel way the randomization method with the stationary detection technique, we develop two new algorithms for the computation of the expected reward rates of finite, irreducible Markov reward models, with control of the relative error. The first algorithm computes the expected transient reward rate and the second one computes the expected averaged reward rate. The algorithms are numerically stable. Further, it is argued that, from the point of view of run-time computational cost, for medium-sized and large Markov reward models, we can expect the algorithms to be better than the only variant of the randomization method that allows to control the relative error and better than the approach that consists in employing iteratively the currently existing algorithms that use the randomization method with stationarity detection but allow to control the absolute error. The performance of the new algorithms is illustrated by means of examples, showing that the algorithms can be not only faster but also more efficient than the alternatives in terms of run-time computational cost in relation to accuracy.     

Matroid optimisation problems with nested non-linear monomials in the objective function

We derive a new approximate version of the alternating direction method of multipliers (ADMM) which uses a relative error criterion. The new version is somewhat restrictive and allows only one of the two subproblems to be minimized approximately, but nevertheless covers commonly encountered special cases. The derivation exploits the long-established relationship between the ADMM and both the proximal point algorithm (PPA) and Douglas–Rachford (DR) splitting for maximal monotone operators, along with a relative-error of the PPA due to Solodov and Svaiter. In the course of analysis, we also derive a version of DR splitting in which one operator may be evaluated approximately using a relative error criterion. We computationally evaluate our method on several classes of test problems and find that it significantly outperforms several alternatives on one problem class.     

An efficient and accurate parallel algorithm for the singular value problem of bidiagonal matrices

Summary. In this paper we propose an algorithm based on Laguerre's iteration, rank two divide-and-conquer technique and a hybrid strategy for computing singular values of bidiagonal matrices. The algorithm is fully parallel in nature and evaluates singular values to tiny relative error if necessary. It is competitive with QR algorithm in serial mode in speed and advantageous in computing partial singular values. Error analysis and numerical results are presented. Received March 15, 1993 / Revised version received June 7, 1994     

GLOBAL CONVERGENCE OF A TRUST REGION ALGORITHM USING INEXACT GRADIENT FOR EQUALITY-CONSTRAINED OPTIMIZATION

1 IntroductionIn this papert we study following nonlinear equlity-constrained optimization problem,where C(x) = (of(x), c200,' t c.(x))"(m 5 n), f, ci: R" -- R are at least twice contimuouslydifferentiable, AC(~) has fllll column rank in the range of interest.There are many trust-region algorithms for problem (1.1), (see [11,[2],[5]), these papershave a same point that is using exact gradient informations, but it is in realistic application.[3] and [41 give a trust region algorithm using i…     

Complexity of fixed points, I

We study the complexity (minimal cost) of computing an s-approximation to a fixed point of a contractive function with the contractive factor q < 1. This is done for the relative error criterion in Part I and for the absolute error criterion in Part II, which is in progress. The complexity depends strongly on the dimension of the domain of functions. For the one-dimensional case we develop an optimal fixed point envelope (FPE) algorithm. The cost of the FPE algorithm with use of the relative error criterion is roughly , where c is the cost of one function evaluation. Thus, for fixed ε and q close to 1 the cost of the FPE algorithm is much smaller than the cost of the simple iteration algorithm, since the latter is roughly For the contractive functions of d variables, with d ≥ log(1/ε)/log(l/q) we show that it is impossible to essentially improve the efficiency of the simple iteration.