Search

Boundary element discretizations of surface and hybrid surface/volume formulations of electromagnetic scattering problems generate large and dense systems of linear equations that are tough to solve by iterative techniques. The restarted generalized minimal residual (GMRES) method is virtually always used when the systems are non-Hermitian and indefinite. However, it may be prohibitively expensive especially for large scale out-of-core integral codes. We present experiments with a novel class of iterative methods that have constant, low memory and algorithmic cost per iteration. The results on some selected matrix problems arising from realistic radar-cross-section calculation indicate that the new family of algorithms is amazingly competitive with the most popular iterative techniques in use today for solving linear systems.

An interesting stabilizing variant of the biconjugate A-orthogonal residual (BiCOR) method is investigated for solving non-Hermitian systems of linear equations in electromagnetics. It is naturally based on and inspired by the composite step strategy employed for the composite step biconjugate gradient method. Our motivation is from the point of view of pivot-breakdown treatment when the BiCOR method has erratic convergence behaviors. The present composite step BiCOR method can reduce the number of spikes in the convergence history of the norm of the residuals to the greatest extent. Moreover, it could provide some further practically desired smoothing behavior towards stabilizing the numerical performance of the BiCOR method.

We present two iterative algorithms for solving real nonsymmetric and complex non-Hermitian linear systems of equations and that were developed from variants of the nonsymmetric Lanczos method. In this paper, we give the theoretical background of the two iterative methods and discuss their main computational aspects. Using a large number of numerical experiments, we analyze their convergence properties, and we also compare them with other popular nonsymmetric iterative solvers in use today.

The Fast Multipole Method was introduced by Greengard and Rokhlin in a seminal paper appeared in 1987 for studying large systems of particle interactions with reduced algorithmic and memory complexity [60]. Developments of the original idea are successfully applied to the analysis of many scientific and engineering problems of practical interest. In scattering analysis, multipole techniques may enable to reduce the computational complexity of iterative solution procedures involving dense matrices arising from the discretization of integral operators from O(n2) to O(n log n) arithmetic operations. In this paper we discuss recent algorithmic developments of algebraic preconditioning techniques for the Fast Multipole Method for 2D and 3D scattering problems. We focus on design aspects, implementation details, numerical scalability, parallel performance on emerging computer systems, and give some minor emphasis to theoretical aspects as well. Thanks to the use of iterative techniques and efficient parallel preconditioners, fast integral solvers involving tens of million unknowns are nowadays feasible and can be integrated in the design processes. Keywords: algebraic preconditioners, Fast Multipole Method, Krylov solvers, electromagnetic scattering applications, Maxwell's equations.

MPEG-4 gives the opportunity to describe the scenes of a motion picture directly through XMT-A and XMT-O: two “high level languages” that are XML based. Moreover MPEG-4 allows (and defines) the opportunities for video streaming. This makes this standard appealing for the conversion of Impress or PowerPoint presentations and also for other e-learning applications because it offers the possibility of publishing the converted presentations on streaming servers (as for example the Darwin server). In this paper we exploit those possibilities by implementing an Impress extension that translates an electronic presentation to XMT-O, so to be finally “compiled” for MPEG-4 conversion, and a streaming architecture for e-learning.

We discuss approximate inverse preconditioners based on Frobenius-norm minimization. We introduce a novel adaptive algorithm based on truncated Neumann matrix expansions for selecting the sparsity pattern of the preconditioner. The construction of the approximate inverse is based on a dual dropping strategy, namely a threshold to drop small entries and a maximum number of nonzero entries per column. We introduce a post-processing stabilization technique to deflate some of the smallest eigenvalues in the spectrum of the preconditioned matrix which can potentially disturb the convergence. Results of preliminary experiments are reported on a set of linear systems arising from different application fields to illustrate the potential of the proposed algorithm for preconditioning effectively iterative Krylov solvers.

We consider iterative solution strategies for solving the Reynolds-Favre averaged Navier-Stokes (RANS) equations on 2D and 3D flow configurations. The novelty of this study is the coupling of an hybrid class of methods for the space discretization, called Fluctuation Splitting (or residual distribution) schemes, and a fully coupled Newton algorithm for solving the RANS equations. This approach is particularly attractive for parallel computations because it gives rise to discretization matrices with a compact stencil resulting in a limited number of nonzero entries. In this paper, we present the solution approach and report on results of numerical experiments with particular emphasis on the design of preconditioners for the inner linear system, which is a critical computational issue of the iterative solution.

With the advent of high-performance parallel computers, boundary integral methods have received an increasing interest for the solution of electromagnetic scattering problems of electrically large objects. The Galerkin discretization of integral equations leads to dense and complex linear systems whose size increases linearly with the dimension of the scatterer and quadratically with the frequency of the illuminating radiation. For solving realistic high-frequency problems, iterative Krylov methods can be a viable alternative to out-of-core direct methods provided they are used in combination with fast algorithms for the matrix–vector products and robust parallel preconditioners. In this paper, we present experiments with iterative Krylov solvers combined with an approximate inverse preconditioner and the fast multipole method for the matrix–vector products. Numerical results on a set of problems arising from realistics radar cross-section calculations in industry illustrate the potential of the proposed strategy for solving large-scale problems in electromagnetism. The research described in this paper has been developed in the framework of a joint collaboration between CERFACS (Toulouse), EADS-CCR (Toulouse), INRIA-CERMICS (Sophia Antipolis). Copyright © 2006 John Wiley & Sons, Ltd.

Motta et al., 2003) proposed a Locally Optimal Vector Quantizer (LPVQ) for lossless encoding of hyperspectral data, in particular, Airborne Visible/Infrared Imaging Spectrometer (AVIRIS) images. In this paper we first show how it is possible to improve the baseline LPVQ algorithm via linear prediction techniques, band reordering and least squares optimization. Then, we use this knowledge to devise a new lossless compression method for AVIRIS images. This method is based on a low complexity, linear prediction approach that exploits the linear nature of the correlation existing between adjacent bands. A simple heuristic is used to detect contexts in which such prediction is likely to perform poorly, thus improving overall compression and requiring only marginal extra storage space. A context modeling mechanism coupled with a one band look ahead capability allows the proposed algorithm to match LPVQ compression performances at a fraction of its space and time requirements. This makes the proposed method suitable to applications where limited hardware is a key requirement, spacecraft on board implementation. We also present a least squares optimized linear prediction for AVIRIS images which, to the best of our knowledge, outperforms any other method published so far.

The boundary element method has become a popular tool for the solution of Maxwell's equations in electromagnetism. From a linear algebra point of view, this leads to the solution of large dense complex linear systems, where the unknowns are associated with the edges of the mesh defined on the surface of the illuminated object. In this paper, we address the iterative solution of these linear systems via preconditioned Krylov solvers. Our primary focus is on the design of an efficient parallelizable preconditioner. In that respect, we consider an approximate inverse method based on the Frobenius-norm minimization. The preconditioner is constructed from a sparse approximation of the dense coefficient matrix, and the patterns both for the preconditioner and for the coefficient matrix are computed a priori using geometric information from the mesh. We describe how such a preconditioner can be naturally implemented in a parallel code that implements the multipole technique for the matrix-vector product calculation. We investigate the numerical scalability of our preconditioner on realistic industrial test problems and show that it exhibits some limitations on very large problems of size close to one million unknowns. To improve its robustness on those large problems we propose an embedded iterative scheme that combines nested GMRES solvers with different fast multipole computations. We show through extensive numerical experiments that this new scheme is extremely robust at affordable memory and CPU costs for the solution of very large and challenging problems.

When encoding low bit-rate video at constant bit-rate, state of the art video encoders may be forced to skip frames. Frames are mostly skipped after "scene changes", i.e. immediately after the beginning of a new scene. We address the problem of determining the minimal number and the exact positions of the frames that must be skipped in a video sequence in order to match closely a prefixed rate and distortion. The reduction of the number of skipped frames decreases the jerkiness associated to the skips and improves the overall quality of the encoded video. The off-line frame-layer rate control method we propose can be used in several existing video coders and it is fully compatible with rate-distortion optimized macroblock-layer rate controls. We also present a simplified heuristic that performs almost optimally while requiring only minimal encoding complexity with respect to the standard encoders.

Recent years have seen a growing interest in the compression of hyperspectral imagery. In a scenario, anticipated by the NOOA for the next generation of GOES satellites, the remote acquisition platform should be able to acquire, compress, and broadcast processed data to final users, all in real time and with limited interaction with a ground station. Here we show how LPVQ, a vector quantizer algorithm previously introduced by the authors, may fit this paradigm when its arithmetic encoder is replaced with the CCSDS lossless data compressor. Beside competitive compression, this algorithm has several other interesting properties. It can be easily implemented in parallel, a number of entropy coding schemes can be used to achieve different complexity/performance tradeoffs, and the compressed stream can be used directly to perform nearest neighborhood pixel search without the need of full decompression.

We present an algorithm for hyperspectral image compression that uses linear prediction in the spectral domain. In particular, we use a least squares optimized linear prediction method with spatial and spectral support. The performance of the predictor is competitive with the state of the art, even when the size of the prediction context is kept to a minimum; therefore the proposed method is suitable to spacecraft on-board implementation, where limited hardware and low power consumption are key requirements. With one band look-ahead capability, the overall compression of the proposed algorithm improves significantly with marginal usage of additional memory. Experiments on data cubes acquired by the NASA JPL's Airborne Visible/Infrared Imaging Spectrometer (AVIRIS) are presented. In the second part of the paper, we revised some on-going research that aims at coupling linear prediction with polynomial fitting, exponential fitting or interpolation. Current simulations show that further improvement is possible. Furthermore, the two tier prediction allows progressive encoding and decoding. This research is promising, but still in a preliminary stage.

We present a new trellis coded vector residual quantizer (TCVRQ) that combines trellis coding and vector residual quantization. We propose new methods for computing quantization levels and experimentally analyze the performances of our TCVRQ in the case of still image coding. Experimental comparisons show that our quantizer performs better than the standard tree and exhaustive search quantizers based on the generalized Lloyd algorithm (GLA).

In this paper, we present communication protocols that allow a "learned" sender and a "learned" receiver to communicate on a bidirectional line, compressing files with (static or dynamic) dictionaries initially built independently by the sender and the receiver from those examples of the source output which they have available. We show that this leads to an improvement in compression, paid with a negligible or almost null possibility of communication error.

We review some of our recent work on LZ-based, single-pass, adaptive algorithms for the compression of digital images. Our approach combines dictionary techniques from adaptive lossless text compression with quantization techniques to obtain single-pass, highly adaptive compression algorithms that allow the compression-fidelity tradeoff to be continuously adjusted, and lend themselves to high-speed parallel/hardware implementation.

In past years, there have been several improvements in lossless image compression. All the recently proposed state-of-the-art lossless image compressors can be roughly divided into two categories: single and double-pass compressors. Linear prediction is rarely used in the first category, while TMW, a state-of-the-art double-pass image compressor, relies on linear prediction for its performance. We propose a single-pass adaptive algorithm that uses context classification and multiple linear predictors, locally optimized on a pixel-by-pixel basis. Locality is also exploited in the entropy coding of the prediction error. The results we obtained on a test set of several standard images are encouraging. On the average, our ALPC obtains a compression ratio comparable to CALIC while improving on some images.

We address the problem of improving the scene cut quality in fixed bit-rate real-time video decoding such as is used in the H.263 and MPEG standards. In low bandwidth applications, scene cuts can cause the bits required to encode a single frame to greatly exceed the target average bits per frame, and necessitate the skipping of other frames to provide sufficient time to transmit the scene cut frame. We present an optimal algorithm for minimizing the number of skipped frames and keep the decoding synchronized. Although the algorithm requires additional encoding complexity, there is no change in decoding complexity (in fact, no change to the decoder at all). Experimental results, obtained with a simplified strategy within the framework of H.263+ video encoding, confirm that the method provides an effective alternative to current frame skipping strategies. The overall quality in the presence of scene cuts is improved with respect the TMN-8 rate control. Although the overall bit rate benefits from our method, our focus is to improve the quality of the video where scene cuts occur (by reducing skipped frames and improving decoder synchronization). The approach here can be combined with more sophisticated rate controls, as, for example, the newer rate-distortion optimized TMN-10 and TMN-11.

Constantinescu and Storer (1994) introduced a single-pass vector quantization algorithm that with no specific training or prior knowledge of the data was able to achieve better compression results with respect to the JPEG standard, along with a number of computational advances such as: adjustable fidelity/compression tradeoff, precise guarantees on any l/spl times/l sub-block of the image, and fast table-lookup decoding. We improve that basic algorithm by blending it with the mean shape-gain vector quantization (MSGVQ) compression scheme. This blending allows a slightly better performance in terms of compression and a clear improvement in visual quality.

Summary form only given. Constantinescu and Storer (1994) introduced an adaptive vector quantization algorithm (AVQ) that combines adaptive dictionary techniques with vector quantization (VQ). The algorithm typically equals or exceeds the compression of the JPEG standard on different classes of images and it often outperforms traditional trained VQ. We show how it is possible to improve AVQ on the class of images on which JPEG does best (i.e., "magazine photographs"). The improvement is possible by exploring the similarities in the dictionary built by AVQ. This is achieved by transforming the input vectors in a way similar to the one used in mean-shape-gain VQ (Oehler and Gray, 1993). In MSGVQ each vector x~/spl isin/R/sup n/ is decomposed as x~=g/spl middot/s~+E/sub x//spl middot/1~, where g=/spl par/x~-E/sub x//spl middot/1~/spl par/ and s~=(x~-E/sub x//spl middot/1~)/g; mean, gain and shape are quantized separately. We apply this idea to AVQ, changing the match heuristic: let and be respectively the of the dictionary block b and of the one anchored in p. The entry b is the best match if d(x~/sub p/,x/spl circ/)/spl les/T (x/spl circ/=g/sub p//spl middot/s~/sub b/+E/sub p//spl middot/1~) and its size is maximum. The triple is entropy coded and sent to the decoder. This simple modification of the match heuristic allows AVQ to improve the compression ratio on many images. In some cases this improvement is as high as 60%. Along with the better compression results, there is also an improvement in the overall visual quality of the decoded image, especially at high compression rate.

Summary form only given. We present a new trellis coded vector residual quantizer (TCVRQ) that combines trellis coding and vector residual quantization. Our TCVRQ is a general-purpose sub-optimal vector quantizer with low computational costs and small memory requirement that permits high memory savings when compared to traditional quantizers. Our experiments confirm that TCVRQ is a good compromise between memory/speed requirements and quality and that it is not sensitive to codebook design errors. We propose a method for computing quantization levels and experimentally analyze the performance of our TCVRQ when applied to speech coding at very low bit rates and to direct image coding. We employed our TCVRQ in a linear prediction based speech codec for the quantization of the LP parameters. Several experiments were performed using both SNR and a perceptive measure of distortion known as cepstral distance. The results obtained and some informal listening tests show that nearly transparent quantization can be performed at a rate of 1.9 bits per parameter. The experiments in image coding were performed encoding some 256 gray levels, 512/spl times/512 pixel images using blocks of 3/spl times/3 pixels. Our TCVRQ were compared, on the same training and test sets, to an exhaustive search vector quantizer (built using the generalized Lloyd algorithm) and to a tree quantizer for different coding rates ranging from 3 to 10 bits per block.

In this paper we review the Split-Merge video displacement estimation technique and show how this can be used, given a classification with integer labels of the objects in the first frame of a video sequence, to track this classification along the sequence while doing motion estimation.

We consider symmetric preconditioning strategies for the iterative solution of dense complex symmetric non-Hermitian systems arising in computational electromagnetics. In particular, we report on the numerical behaviour of the classical incomplete Cholesky factorization as well as some of its recent variants and consider also well-known factorized approximate inverses. We illustrate the difficulties that those techniques encounter on the linear systems under consideration and give some clues to explain their disappointing behaviour. We propose two symmetric preconditioned based on Frobenius-norm minimization that use a prescribed sparsity pattern. The numerical and computational efficiency of the proposed preconditioners are illustrated on a set of model problems arising both from academic and from industrial applications. Copyright © 2004 John Wiley & Sons, Ltd.

In this paper we consider a novel class of Krylov projection methods computed from the Lanczos biconjugate A- Orthonormalization procedure for the solution of dense complex non-Hermitian linear systems arising from the Method of Moments discretization of Maxwell's equations. We report on experiments on a set of model problems representative of realistic radar-cross section calculations to show their competitiveness with other popular Krylov solvers, especially when memory is a concern. The results presented in this study will contribute to assess the potential of iterative Krylov methods for solving electromagnetic scattering problems from large structures enriching the database of this technology.

We introduce a novel variant of the Lanczos method for computing a few eigenvalues of sparse and/or dense non-Hermitian systems arising from the discretization of Maxwell- or Helmholtz-type operators in electromagnetics. We develop a Krylov subspace projection technique built upon short-term vector recurrences that does not require full reorthogonalization and can approximate simultaneously both left and right eigenvectors. We report on experiments for solving eigenproblems arising in the analysis of dielectric waveguides and scattering applications from PEC structures. The theoretical and numerical results reported in this study will contribute to highlight the potential and enrich the database of this technology for solving generalized eigenvalue problems in Computational Electromagnetics.

The practical lossless digital image compressors that achieve the best results in terms of compression ratio are also simple and fast algorithms with low complexity both in terms of memory usage and running time. Surprisingly, the compression ratio achieved by these systems cannot be substantially improved even by using image-by-image optimization techniques or more sophisticate and complex algorithms. Meyer and Tischer (1998) were able, with their TMW, to improve some current best results (they do not report results for all test images) by using global optimization techniques and multiple blended linear predictors. Our investigation is directed to determine the effectiveness of an algorithm that uses multiple adaptive linear predictors, locally optimized on a pixel-by-pixel basis. The results we obtained on a test set of nine standard images are encouraging, where we improve over CALIC on some images.

One of the main concerns in a tokamak is the risk of disruptions with asymmetric halo currents flowing partially in the plasma and partially in the surrounding structures. A detailed 3D description of the full torus is therefore needed. This paper proposes a method for the 3D halo current analysis based on an integral formulation, exploiting compression techniques, parallel architectures, and suitable preconditioners. The procedure is shown to work in an ITER-like geometry.

A massive diffusion of positioning devices and services, transmitting and producing spatio-temporal data, raised space complexity problems and pulled the research focus toward efficient and specific algorithms to compress these huge amount of stored or flowing data. Co Tracks algorithm has been projected for a lossy compression of GPS data, exploiting analogies between all their spatio-temporal features. The original contribution of this algorithm is the consideration of the altitude of the track, an elaboration of 3D data and a dynamic vision of the moving point, because the speed, tightly linked to the time, is supposed to be one of the significant parameters in the uniformity search. Minimum Bounding Box has been the tool employed to group data points and to generate the key points of the approximated trajectory. The compression ratio, resulting also after a further Huffman coding, appears attractively high, suggesting new interesting developments of this new technique.

This paper presents fast computational techniques applied to modelling the RFX-mod fusion device. An integral equation model is derived for the current distribution on the active coils of the conducting structures, and the input-output transfer functions are computed. Speed-up factors of about 200 can be obtained on hybrid CPU-GPU parallelization against uniprocessor computation.