Search

Recently, various iterative methods are investigated to achieve linear minimum mean square error (MMSE) detection accuracy for uplink massive multiple-input multiple-output (MIMO) systems. This letter introduces the non-stationary Richardson (NSR) iteration to achieve fast convergence rate, and reduces its complexity with approximate eigenvalues in massive MIMO system. However, when the system scale grows and channel correlation is considered, the performance of NSR method decays obviously. To improve the robustness, this letter further proposes a deeply fused SDNSR algorithm, which effectively overcomes the weakness of NSR method by fully utilizing the information obtained through the steepest descent (SD) method and NSR method. Moreover, the complexity is significantly reduced by adopting matrix-vector multiplication and reusing intermediate results. Simulation results and complexity analysis exhibit that the SDNSR method achieves superior performance with lower complexity compared to the recently reported works.

Aiming at reducing the complexity of minimum mean square error (MMSE) detection in massive multiple-input multiple-output (MIMO) systems, this paper proposes a detection algorithm with high convergence rate and an efficient hardware architecture based on second-order Richardson iteration (SORI). In the proposed algorithm, a pre-iteration-based initialization method is presented to accelerate the convergence without extra complexity. In addition, the approximation of relaxation factor and the log-likelihood ratio (LLR) is introduced to further reduce computing load. Theoretical analysis demonstrates the advantages of the proposed algorithm in fast convergence and low complexity, and simulation results show that the proposed algorithm can efficiently approach MMSE performance. Based on this algorithm, a flexible hardware architecture is designed, which is deeply pipelined to support $128\times U$ ( $8\leq U\leq 32$ ) massive MIMO detection with the configurable number of iterations, and a folded dual-mode systolic array (DMSA) is fully utilized to achieve the flexibility with low hardware consumption. Implemented on Xilinx Virtex-7 FPGA and SMIC 40nm CMOS technology, the proposed detector is competitive in terms of energy and area efficiency compared to state-of-the-art iterative detectors, and it can adapt to the varied channel condition and the number of users in massive MIMO systems.

We study Leja sequences on the unit disc and resulting mapped sequences to conventional domain, ellipses and real intervals, for the problem of relaxation of Richardson iteration. Using simple considerations, we establish upper and lower estimates for the growth of associated Newton polynomials and the so-called residual polynomials. These results broaden the understanding of such sequences and add to results established in Calvetti et al. (Numer. Math. 67(1), 21–40, 1994), Calvetti and Reichel (Numerical Algorithms 11(1-4), 79–98, 1996; J. Comput. Appl. Math. 71(2), 267–286 1996), Fischer and Reichel (Numer. Math. 54(2), 225–242, 1989), Nachtigal et al. (SIAM Journal on Matrix Analysis and Applications 13(3), 796–825, 1992), Reichel (SIAM J. Numer. Anal. 25(6), 1359–1368, 1988), Tal-Ezer (J. Sci. Comput. 4(1), 25–60, 1989). We also propose adaptive strategies for the selection of relaxation parameters that build on fast strategies (Balgama et al., Electron. Trans. Numer. Anal. 7, 124–140, 1998; Reichel, Linear Algebra and its Applications 154-156(C), 389–414, 1991) which are known to be suitable for the problem. In particular a Leja ordering is enforced on the mapped sequences. New strategies for conveniently confining the spectrums of certain matrices arising in PDEs discretization is described and demonstrate the flexibility of the Richardson iteration.

Fast convergent, accurate, computationally efficient, parallelizable, and robust matrix inversion and parameter estimation algorithms are required in many time-critical and accuracy-critical applications such as system identification, signal and image processing, network and big data analysis, machine learning and in many others. This paper introduces new composite power series expansion with optionally chosen rates (which can be calculated simultaneously on parallel units with different computational capacities) for further convergence rate improvement of high order Newton-Schulz iteration. New expansion was integrated into the Richardson iteration and resulted in significant convergence rate improvement. The improvement is quantified via explicit transient models for estimation errors and by simulations. In addition, the recursive and computationally efficient version of the combination of Richardson iteration and Newton-Schulz iteration with composite expansion is developed for simultaneous calculations. Moreover, unified factorization is developed in this paper in the form of tool-kit for power series expansion, which results in a new family of computationally efficient Newton-Schulz algorithms.

Several approximate matrix inversion methods have been used in linear massive MIMO uplink detectors where their convergence rate, performance, and complexity are greatly affected by the initial solution. In this Letter, the authors exploit a stair matrix, instead of a diagonal matrix, in initialising iterative linear minimum mean square error massive MIMO detector based on several approximate matrix inversion methods, namely, the Gauss-Seidel, successive over relaxation, Richardson iteration, and Newton iteration methods. Numerical results show a significant performance enhancement without a burden of extra complexity using a stair matrix over a diagonal matrix in all methods.

The fixed-stress splitting scheme is a popular method for iteratively solving the Biot equations. The method successively solves the flow and mechanics subproblems while adding a stabilizing term to the flow equation, which includes a parameter that can be chosen freely. However, the convergence properties of the scheme depend significantly on this parameter and choosing it carelessly might lead to a very slow, or even diverging, method. In this paper, we present a way to exploit the matrix structure arising from discretizing the equations in the regime of impermeable porous media in order to obtain a priori knowledge of the optimal choice of this tuning/stabilization parameter.

For solving a class of augmented linear systems, we propose a new efficient iteration method, which is called preconditioned Richardson iteration (PR). Under suitable restrictions on the iteration parameters, we prove that the iterative sequences converge to the unique solution of the augmented linear system. Moreover, the optimal iteration parameters and the corresponding optimal convergence factor are discussed in detail. Numerical results show that the PR iteration method has an advantage over several other iteration methods by computing with the preconditioned GMRES methods from the point of view of iteration steps and CPU times.

Based on the kernel-free boundary integral method proposed by Ying and Henriquez (J Comput Phys 227(2):1046---1074, 2007), which is a second-order accurate method for general elliptic partial differential equations, this work develops it to be a fourth-order accurate version for the modified Helmholtz equation. The updated method is in line with the original one. Unlike the traditional boundary integral method, it does not need to know any analytical expression of the fundamental solution or Green's function in evaluation of boundary or volume integrals. Boundary value problems under consideration are reformulated into Fredholm boundary integral equations of the second kind, whose corresponding discrete forms are solved with the simplest Krylov subspace iterative method, the Richardson iteration. During each iteration, a Cartesian grid based nine-point compact difference scheme is used to discretize the simple interface problem whose solution is the boundary or volume integral in the BIEs. The resulting linear system is solved by a fast Fourier transform based solver, whose computational work is roughly proportional to the number of grid nodes in the Cartesian grid used. As the discrete boundary integral equations are well-conditioned, the iteration converges within an essentially fixed number of steps, independent of the mesh parameter. Numerical results are presented to verify the solution accuracy and demonstrate the algorithm efficiency.

The main contribution of present work is to validate the performance of Richardson iteration method for linear equations with symmetric positive definite (SPD) matrix. Meanwhile, Richardson iterati...

In this paper, a double-step scale splitting (DSS) iteration method is proposed to solve a class of complex symmetric of linear equation. Unconditional convergence result is established under appropriate restrictions. Two reciprocal optimal iteration parameters and the corresponding optimal convergence factor are also determined. Numerical experiments on a few model problems are used to verify the effectiveness of the DSS iteration method.

We propose a single-step preconditioned variant of HSS (SPHSS) and an efficient parameterized SPHSS (PSPHSS) iteration method for solving a class of complex symmetric linear systems. Under suitable conditions, we analyze the convergence properties of the SPHSS and PSPHSS iteration methods. Theoretical analysis shows that the minimal upper bounds for the spectral radius of the SPHSS and PSPHSS iteration matrices are less than those of the SHSS and PSHSS iteration matrices when using the optimal parameters, respectively. Numerical results show that the PSPHSS iteration method has comparable advantage over several other iteration methods whether the experimental optimal parameters are used or not.

For solving a class of complex symmetric linear systems, we introduce a new single-step iteration method, which can be taken as a fixed-point iteration adding the asymptotical error (FPAE). In order to accelerate the convergence, we further develop the parameterized variant of the FPAE (PFPAE) iteration method. Each iteration of the FPAE and the PFPAE methods requires the solution of only one linear system with a real symmetric positive definite coefficient matrix. Under suitable conditions, we derive the spectral radius of the FPAE and the PFPAE iteration matrices, and discuss the quasi-optimal parameters which minimize the above spectral radius. Numerical tests support the contention that the PFPAE iteration method has comparable advantage over some other commonly used iteration methods, particularly when the experimental optimal parameters are not used.

In this paper, by extrapolating the modified Hermitian and skew-Hermitian splitting (MHSS) iteration method with a complex relaxation parameter, a complex-extrapolated MHSS (CMHSS) iteration method is present for solving a class of complex singular symmetric of linear equations. We study the semi-convergence properties of the CMHSS iteration method and the extent of the optimal iterative parameters. Furthermore, the convergence conditions also hold for solving nonsingular complex systems. Numerical experiments are given to verify the effectiveness of the CMHSS iteration method for solving both singular and nonsingular complex symmetric systems.

In this paper, the Jacobi and Gauss-Seidel-type iteration methods are proposed for solving the matrix equation A X B = C , which are based on the splitting schemes of the matrices A and B. The convergence and computational cost of these iteration methods are discussed. Furthermore, we give the preconditioned Jacobi and Gauss-Seidel-type iteration methods. Numerical examples are given to demonstrate the efficiency of these methods proposed in this paper.

Massive multiple-input multiple-output (MIMO) is a core technology for 5G and beyond systems. However, symbol detection in massive MIMO requires high complexity matrix inversions. To tackle this problem, a novel and robust low complexity hybrid algorithm (HA) is proposed for uplink symbol detection in massive MIMO systems with a large number of users. Proposed HA integrates two novel techniques; non-stationary Newton iteration (NSNI) and improved sequential Richardson iteration (ISRI), which are proposed in this paper. Newton iteration (NI) is a promising technique for approximate matrix inversion, however, in this paper, Newton iteration (NI) is realized as the stationary iterative method which uses constant step size for all iterations. Consequently, NI suffers from performance-complexity trade-off. To address this issue, NSNI is proposed, which utilizes non-stationary step size that changes at each iteration. Moreover, Richardson iteration is a simple but efficient algorithm for massive MIMO detection, however, RI suffers from intersymbol interference (ISI) which is a major reason for the low performance of RI when the number of users scales up in massive MIMO system. Hence, symbols are updated sequentially to extenuate ISI in RI. In addition, to further improve the performance of RI, optimal step sizes based on each symbol-index in RI are computed and hence, an improved stationary Richardson iteration (ISRI) is introduced. Finally, to further boost bit error rate (BER), NSNI and RI are integrated into pseudo-stationary iterative HA for low complexity symbol detection in massive MIMO systems. Simulation results validate low complexity, superior BER performance and robustness of proposed HA as compared to recently reported several massive MIMO detection techniques, under both perfect and imperfect channel state information at the receiver.

The Landweber iteration is a general method for the solution of linear systems which is widely applied for image reconstructions. The convergence behavior of the Landweber iteration is of both theoretical and practical importance. By the representation of the iterative formula and the convergence results of the Landweber iteration, we derive the optimal relaxation method under the minimization of the spectral radius of the newly derived iterative matrix. We also establish the iterative relaxation strategy to accelerate the convergence for the Landweber iteration when only the biggest singular value is available. As an immediate result, we derive the corresponding results for Richardson's iteration for the symmetric nonnegative definite linear systems. Finally, numerical simulations are conducted to validate the theoretical results. The advantage of the proposed relaxation strategies is demonstrated by comparing with the existing strategies. HighlightsWe derive the optimal relaxation method.We establish the iterative relaxation strategy to accelerate the convergence.We derive the corresponding results for Richardson's iteration.Numerical simulations are conducted to validate the theoretical results.

We study iterative methods for finding the largest Hermitian positive definite solution of the matrix equation X + ź i = 1 m A i ź X - 1 A i = Q . Convergence rates of the basic fixed point iteration, inversion free variants of the basic fixed point iteration, and Stein iteration are considered. Some numerical examples are presented to illustrate the convergence behaviour of the various algorithms.

Coupled poromechanical problems appear in a variety of disciplines, from reservoir engineering to biomedical applications. This work focuses on efficient strategies for solving the matrix systems that result from discretization and linearization of the governing equations. These systems have an inherent block structure due to the coupled nature of the mass and momentum balance equations. Recently, several iterative solution schemes have been proposed that exhibit stable and rapid convergence to the coupled solution. These schemes appear distinct, but a unifying feature is that they exploit the block-partitioned nature of the problem to accelerate convergence. This paper analyzes several of these schemes and highlights the fundamental connections that underlie their effectiveness. We begin by focusing on two specific methods: a fully-implicit and a sequential-implicit scheme. In the first approach, the system matrix is treated monolithically, and a Krylov iteration is used to update pressure and displacement unknowns simultaneously. To accelerate convergence, a preconditioning operator is introduced based on an approximate block-factorization of the linear system. Next, we analyze a sequential-implicit scheme based on the fixed-stress split. In this method, one iterates back and forth between updating displacement and pressure unknowns separately until convergence to the coupled solution is reached. We re-interpret this scheme as a block-preconditioned Richardson iteration, and we show that the preconditioning operator is identical to that used within the fully-implicit approach. Rapid convergence in both the Richardson- and Krylov-based methods results from a particular choice for a sparse Schur complement approximation. This analysis leads to a unified framework for developing solution schemes based on approximate block factorizations. Many classic fully-implicit and sequential-implicit schemes are simple sub-cases. The analysis also highlights several new approaches that have not been previously explored. For illustration, we directly compare the performance and robustness of several variants on a benchmark problem.

Sample-and-hold (S/H) mismatches incur undesired error which affects the time-interleaved analog-to-digital converter(TIADC)‘s performance. A few calibration methods have been proposed for S/H mismatches which either need training signals or cannot apply to the signals with narrow frequency range around the center of the Nyquist band. This paper proposes a statistics-based correction algorithm for S/H mismatch in 2-channel TIADCs. The mismatch parameter is identified by assuming the modulo two quasi-stationary property of the input samples, and the mismatch-induced error is reconstructed by employing variable multipliers and differentiators in Richardson iteration. Simulation results illustrate the effectiveness of the proposed method and the advantage to the method based on input-free band (IFB).

We consider a fictitious domain formulation of an elliptic partial differential equation and approximate the resulting saddle-point system using a nested inexact preconditioned Uzawa iterative algorithm, which consists of three nested loops. In the outer loop the trial space for the Galerkin approximation of the Lagrange multiplier is enlarged. The intermediate loop solves this Galerkin system by a damped preconditioned Richardson iteration. Each iteration of the latter involves solving an elliptic problem on the fictitious domain whose solution is approximated by an adaptive finite element method in the inner loop. We prove that the overall method converges with the best possible rate and illustrate numerically our theoretical findings.

Recently, Wang et al. (2013) proposed an efficient Hermitian and skew-Hermitian splitting (HSS) iteration method to approximate the solution of linear matrix equation. To further improve the efficiency of the HSS method, we in this paper establish a parameterized preconditioned HSS (PPHSS) iteration method by introducing two Hermitian positive definite preconditioners and two more different iteration parameters for the HSS method. The convergence properties of the PPHSS method used for solving linear matrix equation A X B = C are strictly analyzed and the quasi-optimal values of the iteration parameters for the PPHSS method are also derived. Numerical results demonstrate the feasibility and the efficiency of the PPHSS iteration method.

Summary The paper deals with the numerical solution of Biot's equations of coupled consolidation obtained by a mixed formulation combining continuous Galerkin finite-element and multipoint flux approximation finite-volume methods. The solution algorithm relies on the recently developed fixed-stress solution scheme, in which first the flow problem and then the mechanical one are addressed iteratively. We show that the algorithm can be interpreted as a particular block triangular preconditioning strategy applied within a Richardson iteration. The key component to the success of the preconditioner is the sparse approximation to the Schur complement based on a pressure space mass matrix scaled by a weighting factor that depends element-wise on the inverse of a suitable bulk modulus. The accuracy of the method is assessed, making use of well-known analytical solutions from the literature. Numerical results demonstrate robustness and low computational cost of the fixed-stress scheme in accurately capturing the two-way coupling between deformation and pressure. Copyright © 2015 John Wiley & Sons, Ltd.

We introduce a preconditioner that can be both constructed and applied using only the ability to apply the underlying operator. Such a preconditioner can be very attractive in scenarios where one has a highly efficient parallel code for applying the operator. Our method constructs a polynomial preconditioner using a nonlinear least squares (NLLS) algorithm. We show that this polynomial-based NLLS-optimized (PBNO) preconditioner significantly improves the performance of a discontinuous Galerkin (DG) compressible Euler equation model when run in an implicit---explicit time integration mode; note that IMEX methods are valuable only for low Mach number flows. The PBNO preconditioner achieves significant reduction in GMRES iteration counts and model wall-clock time, and significantly outperforms several existing types of generalized (linear) least squares polynomial preconditioners. Comparisons of the ability of the PBNO preconditioner to improve DG model performance when employing the Stabilized Biconjugate Gradient algorithm (BICGS) and the basic Richardson iteration are also included. In particular, we show that higher order PBNO preconditioning of the Richardson iteration (run in a dot product free mode) makes the algorithm competitive with GMRES and BICGS in a serial computing environment. Because the NLLS-based algorithm used to construct the PBNO preconditioner can handle both positive definite and complex spectra without any need for algorithm modification, we suggest that the PBNO preconditioner is, for certain types of problems, an attractive alternative to existing polynomial preconditioners based on linear least-squares methods.

Inthis paper, amodulus-basedgeneralizedskew-Hermitiantriangularsplit- ting (MGSTS) iteration method is present for solving a class of linear complemen- tarity problems with the system matrix either being an H+-matrix with non-positive off-diagonal entries or a symmetric positive definite matrix. The convergence of the MGSTS iteration method is studied in detail. By choosing differentparameters, a series of existing and new iterative methods arederived, including the modulus-based Jacobi (MJ) and the modulus-based Gauss-Seidel (MGS) iteration methods and so on. Exper- imental results are given to show the effectiveness and feasibility of the new method when it is employed for solving this class of linear complementarity problems.

In this paper, multilevel Jacobi and Gauss–Seidel type iteration methods with compression technique are developed for solving ill-posed integral equations by making use of the multiscale structure of the matrix representation of the integral operator. The methods are based on the combination of Tikhonov regularization and multiscale Galerkin methods, and lead to fast solutions of discrete regularization methods for the equations. Choice for an a posteriori regularization parameter is proposed. An optimal convergence order for the method with the choices of parameters is established. Numerical experiments are given to illustrate the efficiency of the method.

We analyze inexact fixed-point iterations where the generating function contains an inexact solve of an equation system to answer the question of how tolerances for the inner solves influence the iteration error of the outer fixed-point iteration. Important applications are the Picard iteration and partitioned fluid-structure interaction. For the analysis, the iteration is modeled as a perturbed fixed-point iteration, and existing analysis is extended to the nested case x=F(S(x)). We prove that if the iteration converges, it converges to the exact solution irrespective of the tolerance in the inner systems, provided that a nonstandard relative termination criterion is employed, whereas standard relative and absolute criteria do not have this property. Numerical results demonstrate the effectiveness of the approach with the nonstandard termination criterion. (Less)

The work presents an adaptation of iteration method for solving a class of thirst order partial nonlinear differential equation with mixed derivatives.The class of partial differential equations present here is not solvable with neither the method of Green function, the most usual iteration methods for instance variational iteration method, homotopy perturbation method and Adomian decomposition method, nor integral transform for instance Laplace,Sumudu, Fourier and Mellin transform. We presented the stability and convergence of the used method for solving this class of nonlinear chaotic equations.Using the proposed method, we obtained exact solutions to this kind of equations.

submitted to SIAM J. Sci. Comp.; International audience; We present an accelerated algorithm for the solution of static Hamilton-Jacobi-Bellman equations related to optimal control problems. Our scheme is based on a classic policy iteration procedure, which is known to have superlinear convergence in many relevant cases provided the initial guess is sufficiently close to the solution. In many cases, this limitation degenerates into a behavior similar to a value iteration method, with an increased computation time. The new scheme circumvents this problem by combining the advantages of both algorithms with an efficient coupling. The method starts with a value iteration phase and then switches to a policy iteration procedure when a certain error threshold is reached. A delicate point is to determine this threshold in order to avoid cumbersome computation with the value iteration and, at the same time, to be reasonably sure that the policy iteration method will finally converge to the optimal solution. We analyze the methods and efficient coupling in a number of examples in dimension two, three and four illustrating its properties.

The mode of definition of the error at polynomial Richardson’s extrapolation is described. Along with the table of extrapolations the new magnitudes reflecting expediency and efficiency of extrapolation are entered. On concrete examples it is shown that application of Richardson’s extrapolation to a solution of integral equations has appeared rather effective and gives a solution with a high exactitude. Application of formulas of interpolation leads to a solution in the analytical aspect.

In this paper we revisit the well known and popular Normalized Subband Adaptive Filter (NSAF). Based on an analysis of the algorithm in the mean and using an analysis strategy presented in [1], we find that the NSAF can be seen as a Richardson iteration applied to a preconditioned augmented Wiener-Hopf equation. This equation is formulated in such a way that its convergence speed can be predicted directly from a matrix QT R≂, where QT is a matrix formed as a weighted sum of Toeplitz matrices directly related to the filter banks used and R≂ is a tall, rectangular, autocorrelation matrix. Since the QT R≂ itself is symmetric and Toeplitz, we can make quantitative statements about its convergence speed in much the same way as we can for the least mean square (LMS) algorithm with the important difference that in the NSAF case we can directly use QT to control the convergence speed. Through some experiments we demonstrate the validity of our approach in the prediction of convergence speed. Also, and perhaps more important, we point out that our formalism holds the potential for providing an optimization problem such that the filter banks used in NSAF can be designed based on this rather than merely being selected/postulated as is done presently.

The purpose of the current work is to find numerical solutions of the steady state inhomogeneous Vlasov equation. This problem has a wide range of applications in the kinetic simulation of non-thermal plasmas. However, the direct application of either time stepping schemes or iterative methods (such as Krylov-based methods such as the generalized minimal residual method (GMRES) or relaxation schemes) is computationally expensive. In the former case the slowest time scale in the system forces us to perform a long time integration while in the latter case a large number of iterations is required. In this paper we propose a preconditioner based on an alternating direction implicit type splitting method. This preconditioner is then combined with both GMRES and Richardson iteration. The resulting numerical schemes scale almost ideally (i.e. the computational effort is proportional to the number of grid points). Numerical simulations conducted show that this can result in a speed-up of close to two orders of magnitude (even for intermediate grid sizes) with respect to the unpreconditioned case. In addition, we discuss the characteristics of these numerical methods and show the results for a number of numerical simulations.

Summary We consider hybrid deterministic-stochastic iterative algorithms for the solution of large, sparse linear systems. Starting from a convergent splitting of the coefficient matrix, we analyze various types of Monte Carlo acceleration schemes applied to the original preconditioned Richardson (stationary) iteration. These methods are expected to have considerable potential for resiliency to faults when implemented on massively parallel machines. We establish sufficient conditions for the convergence of the hybrid schemes, and we investigate different types of preconditioners including sparse approximate inverses. Numerical experiments on linear systems arising from the discretization of partial differential equations are presented.

Perturbation iteration method has been recently constructed and it has been also proven that this technique is very effective for solving some nonlinear differential equations. In this study, we develop the new optimal perturbation iteration method based on the perturbation iteration algorithms for the approximate solutions of nonlinear differential equations of many types. This work will greatly improve the computational efficiency of the perturbation iteration method. Applications also show that only a few terms are required to get an approximate solution which is more accurate and efficient than many other methods in literature. © 2017 Author(s).

The residual iteration method is a kind of direct projection methods commonly used for solving the quadratic eigenvalue problem. The convergence criterion of the residual iteration method was established, and the impact of shift point and subspace expansion on the convergence of this method has been analyzed. In the process of expanding subspace, this method needs to solve a linear system at every step. For large scale problems in which the equations cannot be solved directly, an inner and outer iteration version of the residual iteration method was proposed. The new method uses the iterative method to solve the equations and uses the approximate solution to expand the subspace. Based on analyzing the relationship between inner and outer iterations, a quantitative criterion for the inner iteration was established which can ensure the convergence of the outer iteration. Finally, the numerical experiments confirm the theory.

A method for solving linear systems of equations with sign-definite self-adjoint operator matrix by the Richardson iteration method in case of the absence of information about the lower spectral bound of a problem is presented. The algorithm is based on the simultaneous operation of two competing iterative processes, the effectiveness of which is constantly analyzed. The method is explained on an example of one-dimensional steady-state heat equation.

The multigrid solution of coupled porous media and Stokes flow problems is considered. The Darcy equation as the saturated porous medium model is coupled to the Stokes equations by means of appropriate interface conditions. We focus on an efficient multigrid solution technique for the coupled problem, which is discretized by finite volumes on staggered grids, giving rise to a saddle point linear system. Special treatment is required regarding the discretization at the interface. An Uzawa smoother is employed in multigrid, which is a decoupled procedure based on symmetric Gauss–Seidel smoothing for velocity components and a simple Richardson iteration for the pressure field. Since a relaxation parameter is part of a Richardson iteration, local Fourier analysis is applied to determine the optimal parameters. Highly satisfactory multigrid convergence is reported, and, moreover, the algorithm performs very well for small values of the hydraulic conductivity and fluid viscosity, which are relevant for applications.

In this paper, the iteration perturbation method is applied to solve nonlinear oscillations. Two examples are given to illustrate the effectiveness and convenience of this iteration procedure. Comparison with the numerical solutions is also presented, revealing that this iteration leads to accurate solutions.

We give the characterization of set-valued iteration semigroups which are the counterparts of the fundamental form of continuous iteration semigroups of single-valued functions on an interval.

A fixed matrix iteration algorithm was proposed by A. Dax (Numer. Algor. 50, 97---114 2009) for solving linear inequalities in a least squares sense. However, a great deal of computation for this algorithm is required, especially for large-scale problems, because a least squares subproblem should be solved accurately at each iteration. We present a modified method, the inexact fixed iteration method, which is a generalization of the fixed matrix iteration method. In this inexact iteration process, the classical LSQR method is implemented to determine an approximate solution of each least squares subproblem with less computational effort. The convergence of this algorithm is analyzed and several numerical examples are presented to illustrate the efficiency of the inexact fixed matrix iteration algorithm for solving large linear inequalities.

A Crank–Nicolson type scheme, which is of order two with respect to all independent variables, is used in the numerical solution of multi-dimensional advection equations. Normally, the order of accuracy of any numerical scheme can be increased by one when the well-known Richardson Extrapolation is used. It is proved that in this particular case the order of accuracy of the combined numerical method, the method consisting of the Crank–Nicolson scheme and the Richardson Extrapolation, is not three but four.

The aim of this paper is two-fold. First, we propose an efficient implementation of the continuous time waveform relaxation (WR) method based on block Krylov subspaces. Second, we compare this new WR-Krylov implementation against Krylov subspace methods combined with the shift and invert (SAI) technique. Some analysis and numerical experiments are presented. Since the WR-Krylov and SAI-Krylov methods build up the solution simultaneously for the whole time interval and there is no time stepping involved, both methods can be seen as iterative across-time methods. The key difference between these methods and standard time integration methods is that their accuracy is not directly related to the time step size.

In this paper we investigate and compare the variational iteration method and the successive approximations method for solving a class of nonlinear differential equations. We prove that these two methods are equivalent for solving these types of equations.

The linearization of nonlinear systems is an important digital enhancement technique. In this paper, a real-time capable post- and pre-linearization method for the widely applicable time-varying discrete-time Volterra series is presented. To this end, an alternative view on the Volterra series is established, which enables the utilization of certain modified linear iterative methods for linearization. For one particular linear iterative method, the Richardson iteration, the corresponding post- and pre-linearizers are discussed in detail. It is motivated that the resulting algorithm can be regarded as a generalization of some existing methods. Furthermore, a simply verifiable condition for convergence is presented, which allows the straightforward evaluation of applicability. The proposed method is demonstrated by means of the linearization of a time-varying nonlinear amplifier, which highlights its capability of linearizing significantly distorted signals, illustrates the advantageous convergence behavior, and depicts its robustness against modeling errors.

This paper is concerned with a modified version of the generalization of positive-definite and skew-Hermitian splitting iteration (MGPSS) to solve the non-Hermitian positive definite linear systems. The theoretical analysis shows that the MGPSS iteration method will converge unconditionally. Numerical examples are reported to confirm the efficiency of the proposed methods.

This paper aims to develop a fast multigrid (MG) solver for a Fredholm integral equation of the first kind, arising from the 2D elastic frictional contact problem. After discretization on a rectangular contact area, the integral equation gives rise to a linear system with the coefficient matrix being dense, symmetric positive definite and Toeplitz. A so-called fast Fourier transform (FFT) smoother is proposed. This is based on a preconditioner M that approximates the inverse of the original coefficient matrix, and that is determined using the FFT technique. The iterates are then updated by Richardson iteration: adding the current residuals preconditioned with the Toeplitz preconditioner M. The FFT smoother significantly reduces most components of the error but enlarges several smooth components. This causes divergence of the MG method. Two approaches are studied to remedy this feature: subdomain deflation (SD) and row sum modification (RSM). MG with the FFT + RSM smoother appears to be more efficient than using the FFT + SD smoother. Moreover, the FFT + RSM smoother can be applied as an efficient iterative solver itself. The two methods related to RSM also show rapid convergence in a test with a wavy surface, where the Toeplitz structure is lost.

In this paper, we propose a parameterized splitting (PS) iteration method for solving complex symmetric linear systems. The convergence theory of the method is established and the spectral properties of the corresponding iteration matrix are analyzed. The explicit expression for the spectral radius of the iteration matrix is given. In addition, the optimal choice of the iteration parameter is discussed. It is shown that the eigenvalues of the preconditioned matrix are cluster at 1. Numerical experiments illustrate the theoretical results and also examine the numerical effectiveness of the new parameterized splitting iteration method served either as a preconditioner or as a solver.

Based on a fourth order compact difference scheme, a Richardson cascadic multigrid (RCMG) method for 2D Poisson equation is proposed, in which the an initial value on the each grid level is given by the Richardson extrapolation technique (Wang and Zhang (2009)) and a cubic interpolation operator. The numerical experiments show that the new method is of higher accuracy and less computation time.

We formulate the 2-Lagrange multiplier method for the Richards equation in heterogeneous soil. This allows a rigorous formulation of a discrete version of the Richards equation on subdomain decompositions involving cross points. Using Kirchhoff transformation, the individual subdomain problems can be transformed into convex minimization problems and solved efficiently using a monotone multigrid method. We discuss and compare weak formulations of the time-discrete and fully discretized multidomain problem. It is shown that in the case of two subdomains, when solving the resulting discrete system with a Richardson iteration, the new method is equivalent to a parallel version of the nonlinear Robin method for the Richards equation proposed in [H. Berninger and O. Sander, Comput. Vis. Sci., 13 (2010), pp. 187--205]. We give numerical results for a problem with realistic soil parameters.