A new matrix splitting preconditioner for generalized saddle point problems

For generalized saddle point problems, we establish a new matrix splitting preconditioner and give the implementing process in detail. The new preconditioner is much easier to be implemented than the modified dimensional split (MDS) preconditioner. The convergence properties of the new splitting iteration method are analyzed. The eigenvalue distribution of the new preconditioned matrix is discussed and an upper bound for the degree of its minimal polynomial is derived. Finally, some numerical examples are carried out to verify the effectiveness and robustness of our preconditioner on generalized saddle point problems discretizing the incompressible Navier–Stokes equations.     

Two augmentation preconditioners for nonsymmetric and indefinite saddle point linear systems with singular (1, 1) blocks

In this paper, two preconditioners based on augmentation are introduced for the solution of large saddle point-type systems with singular (1, 1) blocks. We study the spectral characteristics of the preconditioners, show that all eigenvalues of preconditioned matrices are strongly clustered. Finally, numerical experiments are also reported for illustrating the efficiency of the presented preconditioners.     

Parameterized generalized shift-splitting preconditioners for nonsymmetric saddle point problems

To solve nonsymmetric saddle point problems, the parameterized generalized shift-splitting (PGSS) preconditioner is presented and analyzed. The corresponding PGSS iteration method can be applied not only to the nonsingular saddle point problems but also to the singular ones. The convergence and semi-convergence of the PGSS iteration method are discussed carefully. Meanwhile, the spectral properties of the preconditioned matrix and the strategy of the choices of the parameters are given. Numerical experiments further demonstrate that the PGSS iteration method and the PGSS preconditioner are efficient and have better performance than some existing iteration methods and newly proposed preconditioners, respectively, for solving both the nonsingular and singular nonsymmetric saddle point problems.     

On SSOR-like preconditioner for saddle point problems with dominant skew-Hermitian part

ABSTRACT

Based on the SSOR-like iteration method proposed by Bai [Numer. Linear Algebra Appl. 23 (2016), pp. 37–60], we present an SSOR-like preconditioner for the saddle point problems whose coefficient matrix has strongly dominant skew-Hermitian part. The spectral properties, including the bounds on the eigenvalues of the preconditioned matrix, are discussed in this work. Numerical experiments are presented to illustrate the effectiveness of the new preconditioner for saddle point problems.     

A note on block-diagonally preconditioned PIU methods for singular saddle point problems

Recently, Bai and Wang [On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl. 428 (2008), pp. 2900–2932] and Gao and Kong [Block diagonally preconditioned PIU methods of saddle point problems, Appl. Math. Comput. 216 (2010), pp. 1880–1887] discussed the parameterized inexact Uzawa (PIU) method and the preconditioned parameterized inexact Uzawa (PPIU) method. In this paper, we further study the block-diagonally preconditioned PIU methods for solving singular saddle point problems, and give the corresponding convergence analysis.     

The improvements of the generalized shift-splitting preconditioners for non-singular and singular saddle point problems

ABSTRACT

To solve the saddle point problems with symmetric positive definite (1,1) parts, the improved generalized shift-splitting (IGSS) preconditioner is established in this paper, which yields the IGSS iteration method. Theoretical analysis shows that the IGSS iteration method is convergent and semi-convergent unconditionally. The choices of the iteration parameters are discussed. Moreover, some spectral properties, including the eigenvalue and eigenvector distributions of the preconditioned matrix are also investigated. Finally, numerical results are presented to verify the robustness and the efficiency of the proposed iteration method and the corresponding preconditioner for solving the non-singular and singular saddle point problems.     

On parameterized matrix splitting preconditioner for the saddle point problems

In this paper, we present a parameterized matrix splitting (PMS) preconditioner for the large sparse saddle point problems. The preconditioner is based on a parameterized splitting of the saddle point matrix, resulting in a fixed-point iteration. The convergence theorem of the new iteration method for solving large sparse saddle point problems is proposed by giving the restrictions imposed on the parameter. Based on the idea of the parameterized splitting, we further propose a modified PMS preconditioner. Some useful properties of the preconditioned matrix are established. Numerical implementations show that the resulting preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as generalized minimal residual method.     

A new approach for solving singular systems in topology optimization using Krylov subspace methods

In topology optimization, elements without any contribution to the improvement of the objective function vanish by decrease of density of the design parameter. This easily causes a singular stiffness matrix. To avoid the numerical breakdown caused by this singularity, conventional optimization techniques employ additional procedures. These additional procedures, however, raise some problems. On the other hand, convergence of Krylov subspace methods for singular systems have been studied recently. Through subsequent studies, it has been revealed that the conjugate gradient method (CGM) does not converge to the local optimal solution in some singular systems but in those satisfying certain condition, while the conjugate residual method (CRM) yields converged solutions in any singular systems. In this article, we show that a local optimal solution for topology optimization is obtained by using the CRM and the CGM as a solver of the equilibrium equation in the structural analysis, even if the stiffness matrix becomes singular. Moreover, we prove that the CGM, without any additional procedures, realizes convergence to a local optimal solution in that case. Computer simulation shows that the CGM gives almost the same solutions obtained by the CRM in the case of the two-bar truss problem.     

On the semi-convergence of preconditioned GLHSS iteration method for non-Hermitian singular saddle point problem

Recently, Fan and Zheng studied the preconditioned generalized local Hermitian and skew-Hermitian splitting (GLHSS) iteration method for non-Hermitian singular saddle point problem, and given its semi-convergence conditions; see Fan and Zheng (2014). In this note, we prove the semi-convergence of preconditioned GLHSS method by another method. The obtained result shows that the conditions for guaranteeing its semi-convergence are easy to check and more weaker.     

A relaxed block-triangular splitting preconditioner for generalized saddle-point problems

For the generalized saddle-point problems, based on a new block-triangular splitting of the saddle-point matrix, we introduce a relaxed block-triangular splitting preconditioner to accelerate the convergence rate of the Krylov subspace methods. This new preconditioner is easily implemented since it has simple block structure. The spectral property of the preconditioned matrix is analysed. Moreover, the degree of the minimal polynomial of the preconditioned matrix is also discussed. Numerical experiments are reported to show the preconditioning effect of the new preconditioner.     

复奇异鞍点问题预条件修正AHSS法的半收敛性

提出了求解一类复奇异鞍点问题的预条件修正AHSS法。研究了所提出的新方法的半收敛性。对任意的正迭代参数,得到了所提出的新方法的半收敛定理。数值实验说明,新方法比HSS法求解鞍点问题时更有效。     

A general class of shift-splitting preconditioners for non-Hermitian saddle point problems with applications to time-harmonic eddy current models

Based on a general splitting of the (1,1) leading block matrix, we first construct a general class of shift-splitting (GCSS) preconditioners for non-Hermitian saddle point problems. Convergence conditions of the corresponding matrix splitting iteration methods and preconditioning properties of the GCSS preconditioned saddle point matrices are analyzed. Then the GCSS preconditioner is specifically applied to the non-Hermitian saddle point problems arising from the finite element discretizations of the hybrid formulations of the time-harmonic eddy current models. With suitable choices of the splittings, the new GCSS preconditioners are easier to implement and have faster convergence rates than the existing shift-splitting preconditioner and its modified variant. Two numerical examples are presented to verify the theoretical results and show effectiveness of the new proposed preconditioners.     

A new iterative method for large sparse saddle point problems

In this short note, the convergence of a new iterative method for the Saddle Point Problem is presented.     

Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations

An important problem that arises in different areas of science and engineering is that of computing the limits of sequences of vectors {x_n}, where with N very large. Such sequences arise, for example, in the solution of systems of linear or nonlinear equations by fixed-point iterative methods, and lim_n→∞x_n are simply the required solutions. In most cases of interest, however, these sequences converge to their limits extremely slowly. One practical way to make the sequences {x_n} converge more quickly is to apply to them vector extrapolation methods. In this work, we review two polynomial-type vector extrapolation methods that have proved to be very efficient convergence accelerators; namely, the minimal polynomial extrapolation (MPE) and the reduced rank extrapolation (RRE). We discuss the derivation of these methods, describe the most accurate and stable algorithms for their implementation along with the effective modes of usage in solving systems of equations, nonlinear as well as linear, and present their convergence and stability theory. We also discuss their close connection with the method of Arnoldi and with GMRES, two well-known Krylov subspace methods for linear systems. We show that they can be used very effectively to obtain the dominant eigenvectors of large sparse matrices when the corresponding eigenvalues are known, and provide the relevant theory as well. One such problem is that of computing the PageRank of the Google matrix, which we discuss in detail. In addition, we show that a recent extrapolation method of Kamvar et al. that was proposed for computing the PageRank is very closely related to MPE. We present a generalization of the method of Kamvar et al. along with a very economical algorithm for this generalization. We also provide the missing convergence theory for it.     

Three point discretization of order four and six for (du :dx) of the solution of non-linear singular two point boundary value problem

We present finite difference methods of order four and six for the numerical solution of (du/dx) for the non-linear differential equation u″ = f(x,u,u′), 0 < x > 1 subject to the boundary conditions u(0) = A, u(l) =B. The proposed methods require only three grid points and applicable to both singular and non-singular problems. Numerical examples are given to illustrate the methods and their convergence.     

A new entropic method of dimensionality reduction specially designed for multiclass discrimination (DIRECLADIS)

This is a straightforward generalization of the Karhunen-Loève method making it possible to extract those variables which specifically serve the purpose of discriminating classes.     

Tangential Gap Flow (TGF) navigation: A new reactive obstacle avoidance approach for highly cluttered environments

This paper presents a novel reactive collision avoidance method for mobile robots moving in dense and cluttered environments. The proposed method, entitled Tangential Gap flow (TGF), simplifies the navigation problem using a divide and conquer strategy inspired by the well-known Nearness-Diagram Navigation (ND) techniques. At each control cycle, the TGF extracts free openings surrounding the robot and identifies the suitable heading which makes the best progress towards the goal. This heading is then adjusted to avoid the risk of collision with nearby obstacles based on two concepts namely, tangential and gap flow navigation. The tangential navigation steers the robot parallel to the boundary of the closest obstacle while still emphasizing the progress towards the goal. The gap flow navigation safely and smoothly drives the robot towards the free area in between obstacles that lead to the target. The resultant trajectory is faster, shorter and less-oscillatory when compared to the ND methods. Furthermore, identifying the avoidance maneuver is extended to consider all nearby obstacle points and generate an avoidance rule applicable for all obstacle configurations. Consequently, a smoother yet much more stable behavior is achieved. The stability of the motion controller, that guides the robot towards the desired goal, is proved in the Lyapunov sense. Experimental results including a performance evaluation in very dense and complex environments demonstrate the power of the proposed approach. Additionally, a discussion and comparison with existing Nearness-Diagram Navigation variants is presented.     

A new family of metrics for compact, convex (fuzzy) sets based on a generalized concept of mid and spread

One of the most important aspects of the (statistical) analysis of imprecise data is the usage of a suitable distance on the family of all compact, convex fuzzy sets, which is not too hard to calculate and which reflects the intuitive meaning of fuzzy sets. On the basis of expressing the metric of Bertoluzza et al. [C. Bertoluzza, N. Corral, A. Salas, On a new class of distances between fuzzy numbers, Mathware Soft Comput. 2 (1995) 71-84] in terms of the mid points and spreads of the corresponding intervals we construct new families of metrics on the family of all d-dimensional compact convex sets as well as on the family of all d-dimensional compact convex fuzzy sets. It is shown that these metrics not only fulfill many good properties, but also that they are easy to calculate and easy to manage for statistical purposes, and therefore, useful from the practical point of view.     

A new Neuro-Fuzzy Inference System with Dynamic Neurons (NFIS-DN) for system identification and time series forecasting

A new Neuro-Fuzzy Inference System with Dynamic Neurons or NFIS-DN is presented here for discrete time dynamic system identification and time series forecasting problems. The proposed dynamic system based neuron, referred to as Dynamic Neuron (DN) is realized by a discrete-time nonlinear state-space model. The DN is designed such way, that the output considers only the effect of finite past instances, enabling the system with finite memory. The NFIS-DN model has five layers, and DNs are employed only in the layers handling crisp values. The antecedent and the consequent parameters of NFIS-DN are updated using a self-regulated backpropagation through time learning algorithm. The performance evaluation of NFIS-DN has been carried-out using benchmark problems in the areas of nonlinear system identification and time series forecasting. The results are compared with the state-of-the-art method on the neural fuzzy networks. The obtained results clearly suggest that the NFIS-DN performs significantly better while using a smaller or similar number of fuzzy rules. Finally the practical application of the NFIS-DN has been demonstrated using two real-world problems.     

Ring of Masters (ROM): A new ring structure for Bluetooth scatternets with dynamic routing and adaptive scheduling schemes

This paper attempts to address the scatternet problem in Bluetooth through a comprehensive approach. We propose a new decentralized ring structure to combat the formation of traffic bottlenecks. The adopted construction protocol ensures flexibility of node selection and a good level of fault tolerance. The routing protocol combines both simplicity and robustness by taking advantage of the ring structure and relying on the collective memory of piconets to make forwarding and discarding decisions. The intra- and inter-piconet scheduling algorithm, called ROM adaptive scheduling (RAS), dynamically allocates time slots and is responsive to the varying workload conditions. We demonstrate, through analysis and simulations, that the various components of ROM yield a system that has good performance in terms of throughput, latency, delivery, and link utilization.