Two‐level additive Schwarz algorithms for nonlinear complementarity problem with an M‐function

Nonlinear complementarity problem (NCP) is a wide class of problems. In this paper, some two‐level additive Schwarz algorithms for NCPs with an M‐function are developed and analyzed. The algorithms are proved to be convergent monotonically and can reach the solution of the problem within finite steps. They may also offer a possibility of making use of fast nonlinear solvers for solving the subproblems involved in the algorithms. Some preliminary numerical results are reported. Copyright © 2009 John Wiley & Sons, Ltd.     

Finding a subdivision of a prescribed digraph of order 4

The problem of when a given digraph contains a subdivision of a fixed digraph F is considered. Bang‐Jensen et al. [4] laid out foundations for approaching this problem from the algorithmic point of view. In this article, we give further support to several open conjectures and speculations about algorithmic complexity of finding F‐subdivisions. In particular, up to five exceptions, we completely classify for which 4‐vertex digraphs F, the F‐subdivision problem is polynomial‐time solvable and for which it is NP‐complete. While all NP‐hardness proofs are made by reduction from some version of the 2‐linkage problem in digraphs, some of the polynomial‐time solvable cases involve relatively complicated algorithms.     

Direct algorithms to solve the two‐sided obstacle problem for an M‐matrix

In this paper, two direct algorithms for solving the two‐sided obstacle problem with an M‐matrix are presented. The algorithms are well defined and have polynomial computational complexity. Copyright © 2006 John Wiley & Sons, Ltd.     

Preconditioning trace coupled 3d‐1d systems using fractional Laplacian

Multiscale or multiphysics problems often involve coupling of partial differential equations posed on domains of different dimensionality. In this work, we consider a simplified model problem of a 3d‐1d coupling and the main objective is to construct algorithms that may utilize standard multilevel algorithms for the 3d domain, which has the dominating computational complexity. Preconditioning for a system of two elliptic problems posed, respectively, in a three‐dimensional domain and an embedded one dimensional curve and coupled by the trace constraint is discussed. Investigating numerically the properties of the well‐defined discrete trace operator, it is found that negative fractional Sobolev norms are suitable preconditioners for the Schur complement of the system. The norms are employed to construct a robust block diagonal preconditioner for the coupled problem.     

On Switching to H‐Free Graphs

In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H‐free graph. Polynomial‐time algorithms are known for H having at most three vertices or isomorphic to P₄. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP‐complete, thus solving an open problem [Kratochvíl, Ne?et?il and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K_{1, 2}‐free graph by ten forbidden‐induced subgraphs, each having five vertices. We also give the forbidden‐induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees.     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.     

Simulating events of unknown probabilities via reverse time martingales

Let s∈(0,1) be uniquely determined but only its approximations can be obtained with a finite computational effort. Assume one aims to simulate an event of probability s. Such settings are often encountered in statistical simulations. We consider two specific examples. First, the exact simulation of non‐linear diffusions ([ 3 ]). Second, the celebrated Bernoulli factory problem ([ 10 , 13 ]) of generating an f(p)‐coin given a sequence X₁,X₂,… of independent tosses of a p‐coin (with known f and unknown p). We describe a general framework and provide algorithms where this kind of problems can be fitted and solved. The algorithms are straightforward to implement and thus allow for effective simulation of desired events of probability s. Our methodology links the simulation problem to existence and construction of unbiased estimators. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 441–452, 2011     

On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices

The use of matchings is a powerful technique for scaling and ordering sparse matrices prior to the solution of a linear system Ax = b. Traditional methods such as implemented by the HSL software package MC64 use the Hungarian algorithm to solve the maximum weight maximum cardinality matching problem. However, with advances in the algorithms and hardware used by direct methods for the parallelization of the factorization and solve phases, the serial Hungarian algorithm can represent an unacceptably large proportion of the total solution time for such solvers. Recently, auction algorithms and approximation algorithms have been suggested as alternatives for achieving near‐optimal solutions for the maximum weight maximum cardinality matching problem. In this paper, the efficacy of auction and approximation algorithms as replacements for the Hungarian algorithm is assessed in the context of sparse symmetric direct solvers when used in problems arising from a range of practical applications. High‐cardinality suboptimal matchings are shown to be as effective as optimal matchings for the purposes of scaling. However, matching‐based ordering techniques require that matchings are much closer to optimality before they become effective. The auction algorithm is demonstrated to be capable of finding such matchings significantly faster than the Hungarian algorithm, but our ‐approximation matching approach fails to consistently achieve a sufficient cardinality. Copyright © 2015 The Authors Numerical Linear Algebra with Applications Published by John Wiley & Sons Ltd.     

Minimizing synchronization in IDR (s)

IDR (s) is a family of fast algorithms for iteratively solving large nonsymmetric linear systems. With cluster computing and in particular with Grid computing, the inner product is a bottleneck operation. In this paper, three techniques are investigated for alleviating this bottleneck. First, a recently proposed IDR (s) algorithm that is highly efficient and stable is reformulated in such a way that it has a single global synchronization point per iteration step. Second, the so‐called test matrix is chosen so that the work, communication, and storage involving this matrix is minimized in multi‐cluster environments. Finally, a methodology is presented for a‐priori estimation of the optimal value of s using only problem and machine‐based parameters. Numerical experiments applied to a 3D convection–diffusion problem are performed on the DAS‐3 Grid computer, demonstrating the effectiveness of our approach. Copyright © 2011 John Wiley & Sons, Ltd.     

News Algorithms for tensor decomposition based on a reduced functional

We study the least squares functional of the canonical polyadic tensor decomposition for third order tensors by eliminating one factor matrix, which leads to a reduced functional. An analysis of the reduced functional leads to several equivalent optimization problem, such as a Rayleigh quotient or a projection. These formulations are the basis of several new algorithms as follows: the Centroid Projection method for efficient computation of suboptimal solutions and fixed‐point iteration methods for approximating the best rank‐1 and the best rank‐R decompositions under certain nondegeneracy conditions. Copyright © 2013 John Wiley & Sons, Ltd.     

Modular solvers for image restoration problems using the discrepancy principle

Many problems in image restoration can be formulated as either an unconstrained non‐linear minimization problem, usually with a Tikhonov‐like regularization, where the regularization parameter has to be determined; or as a fully constrained problem, where an estimate of the noise level, either the variance or the signal‐to‐noise ratio, is available. The formulations are mathematically equivalent. However, in practice, it is much easier to develop algorithms for the unconstrained problem, and not always obvious how to adapt such methods to solve the corresponding constrained problem. In this paper, we present a new method which can make use of any existing convergent method for the unconstrained problem to solve the constrained one. The new method is based on a Newton iteration applied to an extended system of non‐linear equations, which couples the constraint and the regularized problem, but it does not require knowledge of the Jacobian of the irregularity functional. The existing solver is only used as a black box solver, which for a fixed regularization parameter returns an improved solution to the unconstrained minimization problem given an initial guess. The new modular solver enables us to easily solve the constrained image restoration problem; the solver automatically identifies the regularization parameter, during the iterative solution process. We present some numerical results. The results indicate that even in the worst case the constrained solver requires only about twice as much work as the unconstrained one, and in some instances the constrained solver can be even faster. Copyright © 2002 John Wiley & Sons, Ltd.     

Two‐grid variational multiscale algorithms for the stationary incompressible Navier‐Stokes equations with friction boundary conditions

Two‐grid variational multiscale (VMS) algorithms for the incompressible Navier‐Stokes equations with friction boundary conditions are presented in this article. First, one‐grid VMS algorithm is used to solve this problem and some error estimates are derived. Then, two‐grid VMS algorithms are proposed and analyzed. The algorithms consist of nonlinear problem on coarse grid and linearized problem (Stokes problem or Oseen problem) on fine grid. Moreover, the stability and convergence of the present algorithms are established. Finally, Numerical results are shown to confirm the theoretical analysis. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 546–569, 2017     

On a new family of high‐order iterative methods for the matrix pth root

The main goal of this paper is to approximate the principal pth root of a matrix by using a family of high‐order iterative methods. We analyse the semi‐local convergence and the speed of convergence of these methods. Concerning stability, it is well known that even the simplified Newton method is unstable. Despite it, we present stable versions of our family of algorithms. We test numerically the methods: we check the numerical robustness and stability by considering matrices that are close to be singular and badly conditioned. We find algorithms of the family with better numerical behavior than the Newton and the Halley methods. These two algorithms are basically the iterative methods proposed in the literature to solve this problem. Copyright © 2015 John Wiley & Sons, Ltd.     

On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

A modified pseudospectral method for solving trajectory optimization problems with singular arc

This paper presents a direct method based on Legendre–Radau pseudospectral method for efficient and accurate solution of a class of singular optimal control problems. In this scheme, based on a priori knowledge of control, the problem is transformed to a multidomain formulation, in which the switching points appear as unknown parameters. Then, by utilizing Legendre‐Radau pseudospectral method, a nonlinear programming problem is derived which can be solved by the well‐developed parameter optimization algorithms. The main advantages of the present method are its superior accuracy and ability to capture the switching times. Accuracy and performance of the proposed method are examined by means of some numerical experiments. Copyright © 2016 John Wiley & Sons, Ltd.     

Performance comparisons of greedy algorithms in compressed sensing

Compressed sensing has motivated the development of numerous sparse approximation algorithms designed to return a solution to an underdetermined system of linear equations where the solution has the fewest number of nonzeros possible, referred to as the sparsest solution. In the compressed sensing setting, greedy sparse approximation algorithms have been observed to be both able to recover the sparsest solution for similar problem sizes as other algorithms and to be computationally efficient; however, little theory is known for their average case behavior. We conduct a large‐scale empirical investigation into the behavior of three of the state of the art greedy algorithms: Normalized Iterative Hard Thresholding (NIHT), Hard Thresholding Pursuit (HTP), and CSMPSP. The investigation considers a variety of random classes of linear systems. The regions of the problem size in which each algorithm is able to reliably recover the sparsest solution is accurately determined, and throughout this region, additional performance characteristics are presented. Contrasting the recovery regions and the average computational time for each algorithm, we present algorithm selection maps, which indicate, for each problem size, which algorithm is able to reliably recover the sparsest vector in the least amount of time. Although no algorithm is observed to be uniformly superior, NIHT is observed to have an advantageous balance of large recovery region, absolute recovery time, and robustness of these properties to additive noise across a variety of problem classes. A principle difference between the NIHT and the more sophisticated HTP and CSMPSP is the balance of asymptotic convergence rate against computational cost prior to potential support set updates. The data suggest that NIHT is typically faster than HTP and CSMPSP because of greater flexibility in updating the support that limits unnecessary computation on incorrect support sets. The algorithm selection maps presented here are the first of their kind for compressed sensing. Copyright © 2014 John Wiley & Sons, Ltd.     

Cooperative Strategies for Solving the Bicriteria Sparse Multiple Knapsack Problem

For hard optimization problems, it is difficult to design heuristic algorithms which exhibit uniformly superior performance for all problem instances. As a result it becomes necessary to tailor the algorithms based on the problem instance. In this paper, we introduce the use of a cooperative problem solving team of heuristics that evolves algorithms for a given problem instance. The efficacy of this method is examined by solving six difficult instances of a bicriteria sparse multiple knapsack problem. Results indicate that such tailored algorithms uniformly improve solutions as compared to using predesigned heuristic algorithms.     

Cut problems in graphs with a budget constraint

We study budgeted variants of classical cut problems: the Multiway Cut problem, the Multicut problem, and the k-Cut problem, and provide approximation algorithms for these problems. Specifically, for the budgeted multiway cut and the k-cut problems we provide constant factor approximation algorithms. We show that the budgeted multicut problem is at least as hard to approximate as the sparsest cut problem, and we provide a bi-criteria approximation algorithm for it.     

Sampling and multilevel coarsening algorithms for fast matrix approximations

This paper addresses matrix approximation problems for matrices that are large, sparse, and/or representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsening techniques, possibly combined with random sampling. A multilevel coarsening technique is proposed, which utilizes a hypergraph associated with the data matrix and a graph coarsening strategy based on column matching. We consider a number of standard applications of this technique as well as a few new ones. Among standard applications, we first consider the problem of computing partial singular value decomposition, for which a combination of sampling and coarsening yields significantly improved singular value decomposition results relative to sampling alone. We also consider the column subset selection problem, a popular low‐rank approximation method used in data‐related applications, and show how multilevel coarsening can be adapted for this problem. Similarly, we consider the problem of graph sparsification and show how coarsening techniques can be employed to solve it. We also establish theoretical results that characterize the approximation error obtained and the quality of the dimension reduction achieved by a coarsening step, when a proper column matching strategy is employed. Numerical experiments illustrate the performances of the methods in a few applications.