Binary Image Compression via Monochromatic Pattern Substitution: Sequential and Parallel Implementations

We present a method for compressing binary images via monochromatic pattern substitution. Such method has no relevant loss of compression effectiveness if the image is partitioned into up to a thousand blocks, approximately, and each block is compressed independently. Therefore, it can be implemented on a distributed system with no interprocessor communication. In the theoretical context of unbounded parallelism, interprocessor communication is needed. Compression effectiveness has a bell-shaped behaviour which is again competitive with the sequential performance when the highest degree of parallelism is reached. Finally, the method has a speed-up if applied sequentially to an image partitioned into up to 256 blocks. It follows that such speed-up can be applied to a parallel implementation on a small scale system.     

沿两条内部平行裂纹受压时材料的断裂问题

顺着平面内的平行裂纹受压材料的断裂问题并不能在线性断裂力学的框架内进行描述，Grif-fith－Irvin型或COC型的断裂判据，虽然可以用来处理经典的线性断裂力学，但对本题则完全不适用，这是因为这些压力对应力强度系数没有影响，与裂缝孔隙值也没有关系[1，2]，这一类问题只能采用新的方法，本文的第一作者曾建议过一种新方法，在这一方法中仍然使用了线性关系，但这种线性关系是从变形固体力学中的非线性方程导出的[3，4，5]．这里必须指出，这种方法曾在变形体稳定性问题中广泛地采用过。作为断裂开始的判据，我们采用了裂缝缺陷附近的局部失稳的判据，在这类情况下，我们认为是从失稳过程引发断裂过程的。     

A Low-Complexity Divide-and-Conquer Method for Computing Eigenvalues and Eigenvectors of Symmetric Band Matrices

A framework for an efficient low-complexity divide-and-conquer algorithm for computing eigenvalues and eigenvectors of an n × n symmetric band matrix with semibandwidth b n is proposed and its arithmetic complexity analyzed. The distinctive feature of the algorithm—after subdivision of the original problem into p subproblems and their solution—is a separation of the eigenvalue and eigenvector computations in the central synthesis problem. The eigenvalues are computed recursively by representing the corresponding symmetric rank b(p–1) modification of a diagonal matrix as a series of rank-one modifications. Each rank-one modifications problem can be solved using techniques developed for the tridiagonal divide-and-conquer algorithm. Once the eigenvalues are known, the corresponding eigenvectors can be computed efficiently using modified QR factorizations with restricted column pivoting. It is shown that the complexity of the resulting divide-and-conquer algorithm is O (n ² b ²) (in exact arithmetic).This revised version was published online in October 2005 with corrections to the Cover Date.     

Approximating Scheduling Unrelated Parallel Machines in Parallel

We show how to approximate in NC the problem of scheduling unrelated parallel machines, for a fixed number of machines in which the makespan C _max is the objective function to minimize. We develop an approximate NC algorithm which finds a schedule whose length is at most (1+o(1))(C^* _max + 3 C^* _maxln(2n(n-1)/)), where C*_max denotes the optimal schedule, n the total number of jobs and a small positive constant. Our approach shows how to relate the linear program obtained by relaxing the integer programming formulation of the problem with a linear program formulation that is positive and in the packing/covering form. The established relationship enables us to transfer approximate fractional solutions from the later formulation that is known to be approximable in NC. Then, we show how to obtain an integer approximate solution, i.e. a schedule, from the fractional one, using the randomized rounding technique. We stress that our analysis assumes that the length of the schedule is (ln n) and that the min p _ij and max p _ij values are not too disparate (where p _ij is the time to run job j on machine i).Finally, we show that the same technique can be applied to the general assignment problem with a fixed number of machines and makespan T.     

Uncertainties Quantification and Data Compression in numerical Aerodynamics

We research how uncertainties in the angle of attack, in the Mach number and in the geometry of the airfoil propagate in the solution (pressure, density, velocity etc). To compute different statistical functionals of the solution we build a low-rank response surface. The building algorithm is working on the fly, is based on the QR-decomposition, has drastically reduced memory requirements and linear complexity. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Interpolation and Parallel Lines

Here we consider 3 interpolation problems for homogeneous polynomials in n n + 1 variables (i.e. for zero-dimensional subschemes Z of Pⁿ) in which the scheme Z is contained in a “ small number ” of “ parallel lines ”; here a finite union D₁ ∪ … ∪ D _x ? Pⁿ of lines is called a set of parallel lines if there is P ∈ Pⁿ such that P ∈ D _i for all i.     

Spanning Pre-disks in a Compression Body

A properly embedded essential planar surface P (not a disk) in a compression body V is called a spanning pre-disk with respect to J,if one boundary component of P is lying in (З)+V and all other boundary components of P are lying in (З)_ V and coplanar with J.In this paper,we show that the number of boundary components of spanning pre-disks in a compression body is unbounded.But the number of a maximal collection of spanning pre-disks is bounded.     

State Trajectory Compression in Optimal Control

In optimal control problems with nonlinear time-dependent 3D PDEs, the computation of the reduced gradient by adjoint methods requires one solve of the state equation forward in time, and one backward solve of the adjoint equation. Since the state enters into the adjoint equation, the storage of a 4D discretization is necessary. We propose a lossy compression algorithm using a cheap predictor for the state data, with additional entropy coding of prediction errors. Analytical and numerical results indicate that compression factors around 30 can be obtained without exceeding the FE discretization error. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Compression of Nakajima monomials in type A and C

We describe an explicit crystal morphism between Nakajima monomials and monomials which give a realization of crystal bases for finite dimensional irreducible modules over the quantized enveloping algebra for Lie algebras of type A and C. This morphism provides a connection between arbitrary Nakajima monomials and Kashiwara–Nakashima tableaux. This yields a translation of Nakajima monomials to the Littelmann path model. Furthermore, as an application of our results we define an insertion scheme for Nakajima monomials compatible to the insertion scheme for tableaux.     

Parallel computing in nonconvex programming

In this paper, we are concerned with the development of parallel algorithms for solving some classes of nonconvex optimization problems. We present an introductory survey of parallel algorithms that have been used to solve structured problems (partially separable, and large-scale block structured problems), and algorithms based on parallel local searches for solving general nonconvex problems. Indefinite quadratic programming posynomial optimization, and the general global concave minimization problem can be solved using these approaches. In addition, for the minimum concave cost network flow problem, we are going to present new parallel search algorithms for large-scale problems. Computational results of an efficient implementation on a multi-transputer system will be presented.     

Fast and Parallel Interval Arithmetic

Infimum-supremum interval arithmetic is widely used because of ease of implementation and narrow results. In this note we show that the overestimation of midpoint-radius interval arithmetic compared to power set operations is uniformly bounded by a factor 1.5 in radius. This is true for the four basic operations as well as for vector and matrix operations, over real and over complex numbers. Moreover, we describe an implementation of midpoint-radius interval arithmetic entirely using BLAS. Therefore, in particular, matrix operations are very fast on almost any computer, with minimal effort for the implementation. Especially, with the new definition it is seemingly the first time that full advantage can be taken of the speed of vector and parallel architectures. The algorithms have been implemented in the Matlab interval toolbox INTLAB.     

Instability in Parallel Flows Revisited

An example of an unstable inviscid plane parallel shear flow with classical boundary conditions is presented. The complete unstable spectrum is exhibited using techniques of continued fractions for the shear flow with profile U ( y )=cos  m y . For such flows spectral instability implies nonlinear instability. A three-dimensional generalization is discussed.     

Parallel computing in combinatorial optimization

This is a review of the literature on parallel computers and algorithms that is relevant for combinatorial optimization. We start by describing theoretical as well as realistic machine models for parallel computations. Next, we deal with the complexity theory for parallel computations and illustrate the resulting concepts by presenting a number of polylog parallel algorithms andP-completeness results. Finally, we discuss the use of parallelism in enumerative methods.     

Parallel pure spinors and holonomy

We characterize the spin pseudo-Riemannian manifolds which admit parallel pure spinors by their holonomy groups. In particular, we study the Lorentzian case. To cite this article: A. Ikemakhen, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Parallel and On-Line Graph Coloring

We discover a surprising connection between graph coloring in two orthogonal paradigms: parallel and on-line computing. We present a randomized on-line coloring algorithm with a performance ratio ofO(n/log n), an improvement of factor over the previous best known algorithm of Vishwanathan. Also, from the same principles, we construct a parallel coloring algorithm with the same performance ratio, for the first such result. As a byproduct, we obtain a parallel approximation for the independent set problem.