Query: efficient iterative schemes

Candidate papers:

abstract: We present an efficient scheme for calculating the Kohn Sham ground state of metallic systems using pseudopotentials and a plane wave basis set. In the first part the application of Pulay's DIIS method (direct inversion in the iterative subspace) to the iterative diagonalization of large matrices will be discussed. Our approach is stable, reliable, and minimizes the number of order \mathit{N}}_{\mathrm{atoms}{3} operations. In the second part, we will discuss an efficient mixing scheme also based on Pulay's scheme. A special `metric' and a special `preconditioning' optimized for a plane wave basis set will be introduced. Scaling of the method will be discussed in detail for non self consistent and self consistent calculations. It will be shown that the number of iterations required to obtain a specific precision is almost independent of the system size. Altogether an order \mathit{N}}_{\mathrm{atoms}{2} scaling is found for systems containing up to 1000 electrons. If we take into account that the number of k points can be decreased linearly with the system size, the overall scaling can approach \mathit{N}}_{\mathrm{atoms} We have implemented these algorithms within a powerful package called VASP (Vienna ab initio simulation package) The program and the techniques have been used successfully for a large number of different systems (liquid and amorphous semiconductors, liquid simple and transition metals, metallic and semiconducting surfaces, phonons in simple metals, transition metals, and semiconductors) and turned out to be very reliable. \textcopyright{ 1996 The American Physical Society.
title: Efficient iterative schemes for ab initio total energy calculations using a plane wave basis set.
venue: Physical review. B, Condensed matter
year: 1996

abstract: The iterative solution of large sparse symmetric and unsymmetric linear systems comprises the most time consuming stage when solving many computationally intensive 3D industrial problems. The standard approach to construction of efficient parallel solution methods consists in designing first of all efficient parallel preconditioners. Unfortunately, it is very difficult to find a constructive compromise between parallel properties, preconditioning quality and arithmetic costs for constructing the preconditioner. Another way to enhance the parallelism of the iterative solution methods is related to consideration of block iterative schemes like block CG method introduced by O`Leary and Underwood. Unfortunately, there does not exist any ease approach to choose the optimal block size of such schemes which is optimal with respect to using parallelism, the resulting convergence rate, and the arithmetic costs of one block iteration. We introduce the so called variable Block CG methods and the Variable Block Arnoldi procedure where we can adaptively reduce the current block size without any restarts. This makes it possible to reduce substantially the block size while preserving at the same time the high convergence rate of the block iterative scheme with the original large constant block size.
author_names: Horst D Simon

Alex Yu Yeremin
title: A New Approach to Construction of Efficient Iterative Schemes for Massively Parallel Applications: Variable Block CG and BiCG Methods and Variable Block Arnoldi Procedure
venue: PPSC
year: 1993

abstract: We consider optimal transport based distributionally robust optimization (DRO) problems with locally strongly convex transport cost functions and affine decision rules. Under conventional convexity assumptions on the underlying loss function, we obtain structural results about the value function, the optimal policy, and the worst case optimal transport adversarial model. These results expose a rich structure embedded in the DRO problem (e.g. strong convexity even if the non DRO problem was not strongly convex, a suitable scaling of the Lagrangian for the DRO constraint, etc. which are crucial for the design of efficient algorithms) As a consequence of these results, one can develop efficient optimization procedures which have the same sample and iteration complexity as a natural non DRO benchmark algorithm such as stochastic gradient descent.
author_names: Jose H Blanchet

Karthyek R A Murthy

Fan Zhang
title: Optimal Transport Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes
year: 2018

abstract: In this paper a novel iterative algorithm is presented for the link transmission model, a fast macroscopic dynamic network loading scheme. The algorithm's solutions are defined on a space time discretized grid. Unlike previous numerical schemes there is no hard upper limit on the time step size for the algorithm to be numerically stable, leaving only the trade off between accuracy and interpolation errors. This is a major benefit because mandatory small time steps in existing algorithm (required for numerical tractability) are undesirable in most strategic analyses. They lead to highly increased memory costs on larger network instances and unnecessary complex behaviour. In practice results are often aggregated for storage or analysis, which leads to the loss of computationally expensive detailed information and to the introduction of inconsistencies. The novel iterative scheme is consistent with the modelling assumptions independent of the numerical time step. A second contribution of the iterative procedure is the smart handling of repeated runs, which can be initialized (or warm started) by an earlier solution. For applications, repeatedly loading a network is often needed when evaluating traffic states under changing variables or adjusted parameter settings, or in optimization and equilibration procedures. In these cases the iterative algorithm is initialized with the solution of a previous run and iterations are performed to find a new consistent solution. Pseudo code is provided for both a basic upwind iterative scheme and an extended algorithm that significantly accelerates convergence. The most important computational gains are achieved by ordering and reducing calculations to that part of the network which has changed (most) The properties of the algorithm are demonstrated on a theoretical network as well as on some real world networks.
author_names: Willem W E Himpe

Ruben Corthout

M J Chris Tampere
title: An efficient iterative link transmission model
year: 2016

abstract: Abstract In this paper, we propose an efficient joint iterative detection and decoding (JIDD) scheme with a soft interference cancellation minimum mean squared error (SIC MMSE) based method for a turbo coded multiple input multiple output (MIMO) system. In the proposed method, we activate a loop inside the SIC MMSE based MIMO detection process in addition to the iterative loop between the MIMO detector and turbo decoder, so that the iteration inside the SIC MMSE detection can be performed in parallel to the iterations inside the turbo decoder. Subsequently, soft outputs from each loop is exchanged for next further iteration, and this makes three iterative loops in total. In comparison with the conventional JIDD schemes, employing additional loop inside the MIMO detection process largely contributes to enhance the performance. In addition, the additional loop speeds up the performance convergence and eventually requires smaller overall computational complexity at the same performance.
author_names: Saleem Ahmed

Sooyoung Kim
title: Efficient SIC MMSE MIMO detection with three iterative loops
year: 2017

abstract: This paper presents several soft decision iterative decoding schemes for physical layer network coding (PNC) operated with coded modulation (CM) and bit interleaved coded modulation (BICM) With respect to PNC operated with CM, we consider network coding based channel decoding (NC CD) and multi user complete decoding (MUD NC) for PNC decoding at the relay. Their BICM counterparts are XOR based channel decoding (XOR CD) and MUD XOR, respectively. First, we show that, when the decoding is non iterative, there is a gap between the BICM capacities of both XOR CD and MUD XOR under Gray mapping and the capacities of their CM counterparts, NC CD, and MUD NC. This is in contrast to the conventional point to point communication system, for which the BICM capacity with Gray mapping is known to be very close to the CM capacity, without the need for iterative decoding. Second, we investigate the error performance of iteratively decoded BICM XOR CD and MUD XOR. Extrinsic information transfer chart analysis and simulation results indicate that for these Gray mapped BICM PNC systems, iterative decoding can achieve considerable gains over non iterative decoding. Again, this is in contrast to the Gray mapped BICM point to point communication system, for which iterative decoding provides little gain over non iterative decoding. We further show that Gray mapping gives rise to best PNC rate for MUD XOR and XOR CD systems among several bits to symbol mappings under study. Overall, our results indicate that BICM PNC systems exhibit different decoding behavior from conventional BICM point to point systems. This paper serves as a first foray into the investigation of this issue.
author_names: Pingping Chen

Soung Chang Liew

Long Shi
title: Bandwidth Efficient Coded Modulation Schemes for Physical Layer Network Coding with High Order Modulations
venue: IEEE Transactions on Communications
year: 2017

abstract: A set of multistep iterative methods with increasing order of convergence is presented, for solving systems of nonlinear equations. One of the main advantages of these schemes is to achieve high order of convergence with few Jacobian and functional evaluations, joint with the use of the same matrix of coefficients in the most of the linear systems involved in the process. Indeed, the application of the pseudocomposition technique on these proposed schemes allows us to increase their order of convergence, obtaining new high order, efficient methods. Finally, some numerical tests are performed in order to check their practical behavior.
author_names: Alicia Cordero

Juan Ramon Torregrosa

Maria P Vassileva
title: Increasing the order of convergence of iterative schemes for solving nonlinear systems
venue: J. Comput. Appl. Math.
year: 2013

abstract: Abstract We reconsider Newton's method and two fixed point methods for finding the minimal positive solution of a nonsymmetric algebraic Riccati equation arising from transport theory. We rewrite the subproblem of the Newton and fixed point iterative schemes into an equivalent form with some special structure. By the use of the particular structure of the subproblem, we then present low memory and low complexity versions of these iterative methods with a factored alternating direction implicit iteration. Some properties of eigenvalues for iterative coefficient matrices in solving the subproblem are derived and the convergence of the proposed methods is established. Numerical experiments show that the new iterative schemes are highly efficient to obtain the minimal positive solution. The proposed low memory and low complexity Newton's method is particularly efficient for solving large scale Riccati equation arising from transport theory.
author_names: Bo Yu

Donghui Li

Ning Dong
title: Low memory and low complexity iterative schemes for a nonsymmetric algebraic Riccati equation arising from transport theory
venue: J. Comput. Appl. Math.
year: 2013

abstract: The continuous demands on increased spectral efficiency, higher throughput, lower latency and lower energy in communication systems imposes large challenges on appropriate channel coding schemes and their efficient hardware implementation. Consequently, channel coding is not only a matter of information theory but also more and more knowledge on efficient parallel hardware architectures and underlying semiconductor technology is required. Finally, a deep understanding of the strong interrelation of code structure, decoding algorithms, communications performance and efficient implementation in state of the art semiconductor technology is mandatory. In this paper, we will highlight this strong interrelation on some advanced iterative channel coding techniques, i.e. turbo codes and LDPC codes and demonstrate challenges and limitations with respect to throughput and latency.
author_names: Stefan Scholl

Stefan Weithoffer

Norbert Wehn
title: Advanced iterative channel coding schemes: When Shannon meets Moore
venue: 2016 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC)
year: 2016

abstract: In wireless sensor networks, utilizing the unmanned aerial vehicle (UAV) as a mobile data collector for the sensor nodes (SNs) is an energy efficient technique to prolong the network lifetime. In this letter, considering a general fading channel model for the SN UAV links, we jointly optimize the SNs' wake up schedule and UAV's trajectory to minimize the maximum energy consumption of all SNs, while ensuring that the required amount of data is collected reliably from each SN. We formulate our design as a mixed integer non convex optimization problem. By applying the successive convex optimization technique, an efficient iterative algorithm is proposed to find a sub optimal solution. Numerical results show that the proposed scheme achieves significant network energy saving as compared to benchmark schemes.
author_names: Cheng Zhan

Yong Zeng

Rui Zhang
title: Energy Efficient Data Collection in UAV Enabled Wireless Sensor Network
venue: IEEE Wireless Communications Letters
year: 2018