Analysis of Curve Reconstruction by Meshless Parameterization

This paper proposes and analyzes a method called meshless parameterization for reconstructing curves from unordered point samples. The method solves a linear system of equations based on convex combinations so as to map the sampled points into corresponding parameter values, whose natural ordering provides the ordering of the points. Using the theory of M-matrices, we derive natural conditions on the point sample which guarantee the correct ordering. A sufficient condition is that the underlying curve be tangent-continuous and free of self-intersections and that the sample is dense enough.     

Topological analysis of large networks

This paper offers new concepts for ordering of large surface networks, which so far have essentially been treated using a combinatorial approach rather than relying on their structural interdependence expressed by laws of geometry. It is shown that the Jordan curve theorem can serve as a powerful algorithm to define, for example, the relationship of a network point to the rest of the whole network. Combining this topological principle with utilization of rich metrical network properties, the analysis transforms a network to a strictly ordered set with a distinct hierarchy of components. Every point is supplied with proposed topological indices reflecting the belonging of a point to its defined environment, or topological group(s). Becoming objects of computation and consideration, the groups themselves are attributed to the corresponding coherent and/or girded groups of the following degree of complexity. The numerous point set is now replaced by the essentially lesser natural aggregation of defined images and the created database files gain a great accessibility.     

具有完全并行度的SOR算法

1　引　　言Jacobi和 SOR迭代是求解线性方程组的两类基本的迭代方法 .并行计算机的出现使人们能立刻注意到它们在拥有并行处理性能上的显著差别 .Jacobi迭代因其各个分量的修正相互独立而具有十分明显的内在并行计算特性 .SOR则完全不同 ,其中诸分量的计算是逐个相关的 .由此而导致一般认为 SOR不适合并行处理 ,其内在并行性远不如 Jacobi迭代[1 ] [2 ] .由于 SOR多用于有限差分或有限元方法导致的大型稀疏方程组求解 ,因此 ,利用系数矩阵零元素或非零元素的特殊分布 ,采用红 -黑或多色排序成为实现 SOR并行处理的有效途径 .然而 ,…     

On a geometrical aspect of SOR and the theory of consistent ordering for positive definite matrices

On the basis of a similarity transformation of , the successive overrelaxation operator, a geometrical interpretation of SOR is given. It is shown how the theory of consistent ordering falls into the resulting framework and how connections between SOR and other algorithms can be established.     

A note on a quadratic formulation for linear complementarity problems

In this note, we discuss some properties of a quadratic formulation for linear complementarity problems. Projected SOR methods proposed by Mangasarian apply to symmetric matrices only. The quadratic formulation discussed here makes it possible to use these SOR methods for solving nonsymmetric LCPs. SOR schemes based on this formulation preserve sparsity. For proper choice of a free parameter, this quadratic formulation also preserves convexity. The value of the quadratic function for the solution of original LCP is also known.     

Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm

The matrix completion problem is to recover a low-rank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclear-norm minimization which requires computing singular value decompositions??a task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving large-scale problems, we propose a low-rank factorization model and construct a nonlinear successive over-relaxation (SOR) algorithm that only requires solving a linear least squares problem per iteration. Extensive numerical experiments show that the algorithm can reliably solve a wide range of problems at a speed at least several times faster than many nuclear-norm minimization algorithms. In addition, convergence of this nonlinear SOR algorithm to a stationary point is analyzed.     

Some fuzzy stochastic orderings for fuzzy random variables

A new approach to stochastic ordering of fuzzy random variables is investigated in this paper. The traditional definitions of stochastic ordering, hazard rate ordering, and also mean residual life ordering were extended and proposed the unified indexes to ranking fuzzy random variables. Finally, we study the stochastic ordering of fuzzy order statistics by using our proposed approach and established some properties.     

Block SOR methods for rank-deficient least-squares problems

Many papers have discussed preconditioned block iterative methods for solving full rank least-squares problems. However very few papers studied iterative methods for solving rank-deficient least-squares problems. Miller and Neumann (1987) proposed the 4-block SOR method for solving the rank-deficient problem. Here a 2-block SOR method and a 3-block SOR method are proposed to solve such problem. The convergence of the block SOR methods is studied. The optimal parameters are determined. Comparison between the 2-block SOR method and the 3-block SOR method is given also.     

Stocking and pricing decisions under endogenous demand and reference point effects

In this paper, we study the newsvendor’s pricing and stocking decisions under reference point effects. The demand faced by the newsvendor is endogenous and the customers may also decide to procure the product from an outside option. We characterize the firm’s optimal pricing and stocking decisions. Our analysis reveals a threshold policy on the firm’s ordering and pricing decisions while considering the impact of reference point effects. We also find that as the level of optimism increases, the firm’s optimal ordering level decreases and optimal price increases. We further study the impact of loss aversion on the firm’s ordering and pricing decisions.     

Numerical Solution of an Elliptic Boundary-value Problem in the Complex Variable

A general, non-self-adjoint, complex, elliptic boundary-valueproblem is approximated by a system of complex, finite-differenceequations and solved by SOR techniques. Since transformationsof the complex difference equations to real equations lead tosystems which lack diagonal dominance, the difference equationsare solved iteratively as a complex system. A brief accountof complex SOR theory is provided. This includes block as wellas point methods and, for the complex point Jacobi matrix, thedistribution of the eigenvalues and the proof that there isone eigenvalue pair with maximum modulus are given. Importantconsiderations in the application of complex methods—accuracy,factors influencing convergence and the automatic determinationof convergence factors—are examined.     

On a Class of Lattice Ordered Inverse Semigroups

It is well known that the free group on a non-empty set can be totally ordered and, further, that each compatible latttice ordering on a free group is a total ordering. On the other hand, Saitô has shown that no non-trivial free inverse semigroup can be totally ordered. In this note we show, however, that every free inverse monoid admits compatible lattice orderings which are closely related to the total orderings on free groups.These orderings are natural in the sense that the imposed partial ordering on the idempotents coincides with the natural partial ordering. For this to happen in a lattice ordered inverse semigroup, the idempotents must form a distributive lattice. The method of construction of the lattice orderings on free inverse monoids can be applied to show that naturally lattice ordered inverse semigroups with a given distributive lattice E of idempotents can have arbitrary Green's relation structure. Analogous results hold for naturally -semilatticed inverse semigroups. In this case, there is no restriction on the semilattice E of idempotents.We also show that every compatible lattice ordering on the free monogenic inverse monoid is of the type considered here. This permits us to prove that there are precisely eight distinct compatible lattice orderings on this semigroup. They belong to two families, each of which contains four members, of conjuguate lattice orderings.     

Extrapolated Gauss-Seidel I and SOR methods for least-squares problems

Summary Recently, special attention has been given in the literature, to the problems of accurately computing the least-squares solution of very largescale over-determined systems of linear equations which occur in geodetic applications. In particular, it has been suggested that one can solve such problems iteratively by applying the block SOR (Successive Overrelaxation) and EGS1 (Extrapolated Gauss Seidel 1) plus semi-iterative methods to a linear system with coefficient matrix 2-cyclic or 3-cyclic. The comparison of 2-block SOR and 3-block SOR was made in [1] and showed that the 2-block SOR is better. In [6], the authors also proved that 3-block EGS1-SI is better than 3-block SOR. Here, we first show that the 2-block DJ (Double Jacobi)-SI, GS-SI and EGS1-SI methods are equivalent and all of them are equivalent to the 3-block EGS1-SI method; then, we prove that the composite methods and 2-block SOR have the same asymptotic rate of convergence, but the former has a better average rate of convergence; finally, numerical experiments are reported, and confirm that the 3-block EGS1-SI is better than the 2-block SOR.     

Large deviations ordering of point processes in some queueing networks

Given a stochastic ordering between point processes, say that a p.p. N is smooth if it is less than the Poisson process with the same average intensity for this ordering. In this article we investigate whether initially smooth processes retain their smoothness as they cross a network of FIFO ·/D/1 queues along fixed routes. For the so-called strong variability ordering we show that point processes remain smooth as they proceed through a tandem of quasi-saturated (i.e., loaded to 1) M+·/D/1 queues. We then introduce the Large Deviations ordering, which involves comparison of the rate functions associated with Large Deviations Principles satisfied by the point processes. For this ordering, we show that smoothness is retained when the processes cross a feed-forward network of unsaturated ·/D/1 queues. We also examine the LD characteristics of a deterministic p.p. at the output of an M+·/D/1 queue. This revised version was published online in June 2006 with corrections to the Cover Date.     

On ranking fuzzy sets

A mathematical model describing a fuzzy ordering of fuzzy sets is suggested. In this model an induced fuzzy ordering is defined as the inverse image of the natural linear ordering on real numbers under natural fuzzy correspondence between fuzzy sets and real numbers. The transitivity property of the strict fuzzy ordering associated with the induced fuzzy ordering is established.     

Non-Stationary Ordering Policies for Multi-Item Inventory Systems Subject to a Single Resource Constraint

This paper studies the multi-item inventory problem with a single constraint. Two well-known approaches to this problem are the Lagrangian method and the fixed-cycle approach. Both of these methods generate stationary ordering policies. A competing approach is presented here that generates non-stationary ordering policies, with order quantities that vary over time. These non-stationary policies are, in all cases, preferred to those generated by the Lagrangian approach, and in some cases preferred to those generated by the fixed-cycle approach. Computational results comparing the three methods are also given.     

Ordering fuzzy sets over the real line: An approach based on decision making under uncertainty

The ordering of fuzzy sets over the real line is approached from the point of view of ordering intervals rather than ordering numbers. First, the maximax and maximin criteria which are commonly used for ordering intervals are expressed in terms of characteristic functions. These criteria and the Hurwicz criterion for decision making under complete ignorance are then reformulated in a manner that allows for their generalization to the fuzzy case. Transitivity is established for these ordering rules. A criterion based on the principle of diminishing marginal utility is also presented.     

A multicolour SOR method for the finite-element method

In this paper we present several algorithms to reorder unknowns in a finite-element mesh so that we can use the multicolour SOR method to solve the corresponding linear system on a pipelined computer or on a parallel computer. We also discuss the assembling process by reordering elements with our algorithms. Numerical tests on a pipelined computer indicate the efficiency of the multicolour SOR method.     

红黑排序混合算法收敛速度分析

The algorithm of applying the block Gauss elimination to the Red-Black or-dering matrix to reduce the order of the system then solve the reduced system byiterative methods is called Hybrid Red-Black Ordering algorithm.In this paper,we discuss the convergence rate of the hybrid methods combined with JACOBI,CG,GMRES(m).Theoretical analysis shows that without preconditioner thesethree hybrid methods converge about 2 times as fast as the corresponding natural ordering methods.For the case that all the eigenvalues is near the real axis, the GMRES(m) algorithm converges about 3 times faster than the natural ordering GMRES(m).Various numerical experiments are presented.For large scale prob-lem with preconditioners, numerical experiments show that the GMRES(m) hybrid methods converge from about 3 times to even 5 times as fast as the natural order-ing methods and the computing time is reduced to about 1/3 even 1/6 of that of the natural ordering methods.     

Optimality relationships forp-cyclic SOR

Summary The optimality question for blockp-cyclic SOR iterations discussed in Young and Varga is answered under natural conditions on the spectrum of the block Jacobi matrix. In particular, it is shown that repartitioning a blockp-cyclic matrix into a blockq-cyclic form,q, results in asymptotically faster SOR convergence for the same amount of work per iteration. As a consequence block 2-cyclic SOR is optimal under these conditions.Research supported in part by the US Air Force under Grant no. AFOSR-88-0285 and the National Science Foundation under grant no. DMS-85-21154 Present address: Boeing Computer Services, P.O. Box 24346, MS 7L-21, Seattle, WA 98124-0346, USA     

线性块SOR二级迭代法的收敛性质

内迭代次数充分大时,求解非奇异线性方程组的块SOR二级迭代法与经典的块SOR方法有相同的收敛性和大致相等的收敛速度.因此,用于块SOR方法有效的松弛因子,同样可有效地用于块SOR二级迭代法.