Reorthogonalization for the Golub–Kahan–Lanczos bidiagonal reduction

The Golub–Kahan–Lanczos (GKL) bidiagonal reduction generates, by recurrence, the matrix factorization of $X \in \mathbb{R }^{m \times n}, m \ge n$ , given by $$\begin{aligned} X = UBV^T \end{aligned}$$ where $U \in \mathbb{R }^{m \times n}$ is left orthogonal, $V \in \mathbb{R }^{n \times n}$ is orthogonal, and $B \in \mathbb{R }^{n \times n}$ is bidiagonal. When the GKL recurrence is implemented in finite precision arithmetic, the columns of $U$ and $V$ tend to lose orthogonality, making a reorthogonalization strategy necessary to preserve convergence of the singular values. The use of an approach started by Simon and Zha (SIAM J Sci Stat Comput, 21:2257–2274, 2000) that reorthogonalizes only one of the two left orthogonal matrices $U$ and $V$ is shown to be very effective by the results presented here. Supposing that $V$ is the matrix reorthogonalized, the reorthogonalized GKL algorithm proposed here is modeled as the Householder Q–R factorization of $\left( \begin{array}{c} 0_{n \times k} \\ X V_k \end{array}\right) $ where $V_k = V(:,1:k)$ . That model is used to show that if $\varepsilon _M $ is the machine unit and $$\begin{aligned} \bar{\eta }= \Vert \mathbf{tril }(I-V^T\!~V)\Vert _F, \end{aligned}$$ where $\mathbf{tril }(\cdot )$ is the strictly lower triangular part of the contents, then: (1) the GKL recurrence produces Krylov spaces generated by a nearby matrix $X + \delta X$ , $\Vert \delta X\Vert _F = \mathcal O (\varepsilon _M + \bar{\eta }) \Vert X\Vert _F$ ; (2) singular values converge in the Lanczos process at the rate expected from the GKL algorithm in exact arithmetic on a nearby matrix; (3) a new proposed algorithm for recovering leading left singular vectors produces better bounds on loss of orthogonality and residual errors.     

An outer–inner linearization method for non-convex and nondifferentiable composite regularization problems

Journal of Global Optimization - We propose a new outer–inner linearization method for non-convex statistical learning problems involving non-convex structural penalties and non-convex loss....     

Mesh independent superlinear convergence of an inner–outer iterative method for semilinear elliptic interface problems

We propose the damped inexact Newton method, coupled with preconditioned inner iterations, to solve the finite element discretization of a class of nonlinear elliptic interface problems. The linearized equations are solved by a preconditioned conjugate gradient method. Both the inner and outer iterations exhibit mesh independent superlinear convergence.     

Addendum to: A hybrid conjugate gradient method based on a quadratic relaxation of Dai–Yuan hybrid conjugate gradient parameter

Here, necessary corrections on computing the hybridization parameter of the quadratic hybrid conjugate gradient method of Babaie-Kafaki [S. Babaie-Kafaki, A hybrid conjugate gradient method based on a quadratic relaxation of Dai-Yuan hybrid conjugate gradient parameter, Optimization, DOI: 10.1080/02331934.2011.611512, 2011] are stated in brief. Throughout, we use the same notations and equation numbers as in Babaie-Kafaki (2011).     

A hybrid conjugate gradient method based on a quadratic relaxation of the Dai–Yuan hybrid conjugate gradient parameter

To take advantage of the attractive features of the Hestenes–Stiefel and Dai–Yuan conjugate gradient (CG) methods, we suggest a hybridization of these methods using a quadratic relaxation of a hybrid CG parameter proposed by Dai and Yuan. In the proposed method, the hybridization parameter is computed based on a conjugacy condition. Under proper conditions, we show that our method is globally convergent for uniformly convex functions. We give a numerical comparison of the implementations of our method and two efficient hybrid CG methods proposed by Dai and Yuan using a set of unconstrained optimization test problems from the CUTEr collection. Numerical results show the efficiency of the proposed hybrid CG method in the sense of the performance profile introduced by Dolan and Moré.     

A stabilized structured Dantzig–Wolfe decomposition method

We discuss an algorithmic scheme, which we call the stabilized structured Dantzig–Wolfe decomposition method, for solving large-scale structured linear programs. It can be applied when the subproblem of the standard Dantzig–Wolfe approach admits an alternative master model amenable to column generation, other than the standard one in which there is a variable for each of the extreme points and extreme rays of the corresponding polyhedron. Stabilization is achieved by the same techniques developed for the standard Dantzig–Wolfe approach and it is equally useful to improve the performance, as shown by computational results obtained on an application to the multicommodity capacitated network design problem.     

A Hummel–Seebeck type method for variational inclusions

We study the stability of a Hummel–Seebeck like method for solving variational inclusions of the form 0?∈?f(x)?+?G(x), where f is a single-valued function while G stands for a set-valued mapping, both of them acting in Banach spaces. Then, we investigate a measure of conditioning of these inclusions under canonical perturbations.     

A level-set method for convective–diffusive particle deposition

This article presents a fixed-mesh approach to model convective–diffusive particle deposition onto surfaces. The deposition occurring at the depositing front is modeled as a first order reaction. The evolving depositing front is captured implicitly using the level-set method. Within the level-set formulation, the particle consumed during the deposition process is accounted for via a volumetric sink term in the species conservation equation for the particles. Fluid flow is modeled using the incompressible Navier–Stokes equations. The presented approach is implemented within the framework of a finite volume method. Validations are made against solutions of the total concentration approach for one- and two-dimensional depositions with and without convective effect. The presented approach is then employed to investigate deposition on single- and multi-tube arrays in a cross-flow configuration.     

A generalization of the Bombieri–Pila determinant method

The so-called determinant method was developed by Bombieri and Pila in 1989 for counting integral points of bounded height on affine plane curves. In this paper, we give a generalization of that method to varieties of higher dimension, yielding a proof of Heath-Brown’s “Theorem 14” by real-analytic considerations alone. Bibliography: 11 titles.     

A Levenberg–Marquardt method based on Sobolev gradients

We extend the theory of Sobolev gradients to include variable metric methods, such as Newton’s method and the Levenberg–Marquardt method, as gradient descent iterations associated with stepwise variable inner products. In particular, we obtain existence, uniqueness, and asymptotic convergence results for a gradient flow based on a variable inner product.     

A Vanka-based parameter-robust multigrid relaxation for the Stokes–Darcy Brinkman problems

We consider a block-structured multigrid method based on Braess–Sarazin relaxation for solving the Stokes–Darcy Brinkman equations discretized by the marker and cell scheme. In the relaxation scheme, an element-based additive Vanka operator is used to approximate the inverse of the corresponding shifted Laplacian operator involved in the discrete Stokes–Darcy Brinkman system. Using local Fourier analysis, we present the stencil for the additive Vanka smoother and derive an optimal smoothing factor for Vanka-based Braess–Sarazin relaxation for the Stokes–Darcy Brinkman equations. Although the optimal damping parameter is dependent on meshsize and physical parameter, it is very close to one. In practice, we find that using three sweeps of Jacobi relaxation on the Schur complement system is sufficient. Numerical results of two-grid and V(1,1)-cycle are presented, which show high efficiency of the proposed relaxation scheme and its robustness to physical parameters and the meshsize. Using a damping parameter equal to one gives almost the same convergence results as these for the optimal damping parameter.     

A non-uniform Berry–Esseen bound via Stein's method

This paper is part of our efforts to develop Stein's method beyond uniform bounds in normal approximation. Our main result is a proof for a non-uniform Berry–Esseen bound for independent and not necessarily identically distributed random variables without assuming the existence of third moments. It is proved by combining truncation with Stein's method and by taking the concentration inequality approach, improved and adapted for non-uniform bounds. To illustrate the technique, we give a proof for a uniform Berry–Esseen bound without assuming the existence of third moments. Received: 2 March 2000 / Revised version: 20 July 2000 / Published online: 26 April 2001     

A generalized Fourier–Hermite method for the Vlasov–Poisson system

BIT Numerical Mathematics - A generalized Fourier–Hermite semi-discretization for the Vlasov–Poisson equation is introduced. The formulation of the method includes as special cases the...     

A Fourier spectral method for fractional-in-space Cahn–Hilliard equation

In this paper, a fractional extension of the Cahn–Hilliard (CH) phase field model is proposed, i.e. the fractional-in-space CH equation. The fractional order controls the thickness and the lifetime of the interface, which is typically diffusive in integer order case. An unconditionally energy stable Fourier spectral scheme is developed to solve the fractional equation with periodic or Neumann boundary conditions. This method is of spectral accuracy in space and of second-order accuracy in time. The main advantages of this method are that it yields high precision and high efficiency. Moreover, an extra stabilizing term is added to obey the energy decay property while maintaining accuracy and simplicity. Numerical experiments are presented to confirm the accuracy and effectiveness of the proposed method.     

A new method for computing Moore–Penrose inverse matrices

The Moore–Penrose inverse of an arbitrary matrix (including singular and rectangular) has many applications in statistics, prediction theory, control system analysis, curve fitting and numerical analysis. In this paper, an algorithm based on the conjugate Gram–Schmidt process and the Moore–Penrose inverse of partitioned matrices is proposed for computing the pseudoinverse of an m×n$m\times n$ real matrix A$A$ with m≥n$m\ge n$ and rank r≤n$r\le n$. Numerical experiments show that the resulting pseudoinverse matrix is reasonably accurate and its computation time is significantly less than that of pseudoinverses obtained by the other methods for large sparse matrices.     

A Douglas–Rachford splitting method for solving equilibrium problems

We propose a splitting method for solving equilibrium problems involving the sum of two bifunctions satisfying standard conditions. We prove that this problem is equivalent to find a zero of the sum of two appropriate maximally monotone operators under a suitable qualification condition. Our algorithm is a consequence of the Douglas–Rachford splitting applied to this auxiliary monotone inclusion. Connections between monotone inclusions and equilibrium problems are studied.