Search

This paper is concerned with the reformulation of Neumann-Neumann waveform relaxation (NNWR) methods and Dirichlet-Neumann waveform relaxation (DNWR) methods, a family of parallel space-time approaches to solving time-dependent PDEs. By changing the order of the operations, pipeline-parallel computation of the waveform iterates are possible, without changing the solution of each waveform iterate. The parallel efficiency of the pipeline implementation is analyzed, as well as the change in the communication pattern. Numerical studies are presented to show the effectiveness of the pipeline NNWR and DNWR algorithms. [ABSTRACT FROM AUTHOR]

Nonlinear minimization, as a subcase of nonlinear optimization, is an important issue in the research of various intelligent systems. Recently, Zhang et al. developed the continuous-time and discrete-time forms of Zhang dynamics (ZD) for time-varying nonlinear minimization. Based on this previous work, another two discrete-time ZD (DTZD) algorithms are proposed and investigated in this paper. Specifically, the resultant DTZD algorithms are developed for time-varying nonlinear minimization by utilizing two different types of Taylor-type difference rules. Theoretically, each steady-state residual error in the DTZD algorithm changes in an O( τ ) manner with τ being the sampling gap. Comparative numerical results are presented to further substantiate the efficacy and superiority of the proposed DTZD algorithms for time-varying nonlinear minimization. [ABSTRACT FROM AUTHOR]

A nonsmooth Levenberg-Marquard (LM) method with double parameter adjusting strategies is presented for solving vertical complementarity problems based on the computation of an element of a vextor-valued minimum function's B-differential in this paper. At each iteration, the LM parameter is adjusted based on the norm of the vector-valued minimum function and the ratio between the actual reduction and the predicted reduction. Under the local error bound condition, which is strictly weaker than nonsingular assumption, the local convergence rate is discussed. Finally, the numerical tests indicate that the present algorithm is effective. [ABSTRACT FROM AUTHOR]

In some approximation problems, sampling from the target function can be both expensive and time-consuming. It would be convenient to have a method for indicating where approximation quality is poor, so that generation of new data provides the user with greater accuracy where needed. In this paper, we propose a new adaptive algorithm for radial basis function (RBF) interpolation which aims to assess the local approximation quality, and add or remove points as required to improve the error in the specified region. For Gaussian and multiquadric approximation, we have the flexibility of a shape parameter which we can use to keep the condition number of interpolation matrix at a moderate size. Numerical results for test functions which appear in the literature are given for dimensions 1 and 2, to show that our method performs well. We also give a three-dimensional example from the finance world, since we would like to advertise RBF techniques as useful tools for approximation in the high-dimensional settings one often meets in finance. [ABSTRACT FROM AUTHOR]

Tearing is a long-established decomposition technique, widely adapted across many engineering fields. It reduces the task of solving a large and sparse nonlinear system of equations to that of solving a sequence of low-dimensional ones. The most serious weakness of this approach is well-known: It may suffer from severe numerical instability. The present paper resolves this flaw for the first time. The new approach requires reasonable bound constraints on the variables. The worst-case time complexity of the algorithm is exponential in the size of the largest subproblem of the decomposed system. Although there is no theoretical guarantee that all solutions will be found in the general case, increasing the so-called sample size parameter of the method improves robustness. This is demonstrated on two particularly challenging problems. Our first example is the steady-state simulation a challenging distillation column, belonging to an infamous class of problems where tearing often fails due to numerical instability. This column has three solutions, one of which is missed using tearing, but even with problem-specific methods that are not based on tearing. The other example is the Stewart-Gough platform with 40 real solutions, an extensively studied benchmark in the field of numerical algebraic geometry. For both examples, all solutions are found with a fairly small amount of sampling. [ABSTRACT FROM AUTHOR]

In this paper, two splitting extragradient-like algorithms for solving strongly pseudomonotone equilibrium problems given by a sum of two bifunctions are proposed. The convergence of the proposed methods is analyzed and the R-linear rate of convergence under suitable assumptions on bifunctions is established. Moreover, a noisy data case, when a part of the bifunction is contaminated by errors, is studied. Finally, some numerical experiments are given to demonstrate the efficiency of our algorithms. [ABSTRACT FROM AUTHOR]

The paper aims at answering the following question, in the scalar as well in the vector case: What do the famous Aitken's $\Delta ^{2}$ and Wynn's $\varepsilon $-algorithm exactly do with the terms of the input sequence? Inspecting the rules of these algorithms from a geometric point of view leads to change the question into another one: By what kind of geometric object can the parallel (or harmonic) sum be represented? Thus, the paper begins with geometric considerations on the parallel addition and the parallel subtraction of vectors, including equivalent definition, and properties derived from the new point of view. It is shown how the parallel sum of vectors is related to the Bézier parabola controlled by these vectors and to their interpolating equiangular spiral. In the second part, observing that Aitken's $\Delta ^{2}$ and Wynn's $\varepsilon $-algorithm may be defined through hybrid sums, mixing standard and parallel sums, the consequences are drawn regarding the way one can define and analyze these algorithms. New explanatory rules are derived for the $\varepsilon $-algorithm, providing a better understanding of its basic step and of its cross-rule. [ABSTRACT FROM AUTHOR]

We generalize and extend results of the series of papers by Greenbaum and Strakoš (IMA Vol Math Appl 60:95-118, ), Greenbaum et al. (SIAM J Matrix Anal Appl 17(3):465-469, ), Arioli et al. (BIT 38(4):636-643, ) and Duintjer Tebbens and Meurant (SIAM J Matrix Anal Appl 33(3):958-978, ). They show how to construct matrices with right-hand sides generating a prescribed GMRES residual norm convergence curve as well as prescribed Ritz values in all iterations, including the eigenvalues, and give parametrizations of the entire class of matrices and right-hand sides with these properties. These results assumed that the underlying Arnoldi orthogonalization processes are breakdown-free and hence considered non-derogatory matrices only. We extend the results with parametrizations of classes of general nonsingular matrices with right-hand sides allowing the early termination case and also give analogues for the early termination case of other results related to the theory developed in the papers mentioned above. [ABSTRACT FROM AUTHOR]

Error bounds for SB-matrices linear complementarity problems are given in the paper (Dai et al., Numer Algorithms 61:121–139, 2012 ). In this paper, new error bounds for the linear complementarity problem when the matrix involved is an SB-matrix are presented and some sufficient conditions that new bounds are sharper than those of the previous paper under certain assumptions are provided. New perturbation bounds of SB-matrices linear complementarity problems are also considered. [ABSTRACT FROM AUTHOR]

In this paper, we consider a problem of reconstructing an image from incomplete quadratic measurements by minimizing its total variation. The problem of reconstructing an object from incomplete nonlinear acquisitions arises in many applications, such as astronomical imaging or depth reconstruction. Placing ourselves in a discrete setting, we provide theoretical guarantees for stable and robust image recovery from incomplete noisy quadratic measurements. [ABSTRACT FROM AUTHOR]

Mehrotra's algorithm has been the most successful infeasible interior-point algorithm for linear programming since 1990. Most popular interior-point software packages for linear programming are based on Mehrotra's algorithm. This paper describes a proposal and implementation of an alternative algorithm, an arc-search infeasible interior-point algorithm. We will demonstrate, by testing Netlib problems and comparing the test results obtained by the arc-search infeasible interior-point algorithm and Mehrotra's algorithm, that the proposed arc-search infeasible interior-point algorithm is a more reliable and efficient algorithm than Mehrotra's algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider an efficient algorithm for solving a class of boundary value problems with gradient nonlinearity arising from many applications such as non-Darician porous media flows. [ABSTRACT FROM AUTHOR]

In this paper, we apply the Schwarz waveform relaxation (SWR) method to the one-dimensional Schrödinger equation with a general linear or a nonlinear potential. We propose a new algorithm for the Schrödinger equation with time-independent linear potential, which is robust and scalable up to 500 subdomains. It reduces significantly computation time compared with the classical algorithms. Concerning the case of time-dependent linear potential or the nonlinear potential, we use a preprocessed linear operator for the zero potential case as a preconditioner which leads to a preconditioned algorithm. This ensures high scalability. In addition, some newly constructed absorbing boundary conditions are used as the transmission conditions and compared numerically. [ABSTRACT FROM AUTHOR]

In their original paper, Golub and Meurant (BIT 37:687-705, ) suggest to compute bounds for the A-norm of the error in the conjugate gradient (CG) method using Gauss, Gauss-Radau and Gauss-Lobatto quadratures. The quadratures are computed using the (1,1)-entry of the inverse of the corresponding Jacobi matrix (or its rank-one or rank-two modifications). The resulting algorithm called CGQL computes explicitly the entries of the Jacobi matrix and its modifications from the CG coefficients. In this paper, we use the fact that CG computes the Cholesky decomposition of the Jacobi matrix which is given implicitly. For Gauss-Radau and Gauss-Lobatto quadratures, instead of computing the entries of the modified Jacobi matrices, we directly compute the entries of the Cholesky decompositions of the (modified) Jacobi matrices. This leads to simpler formulas in comparison to those used in CGQL. [ABSTRACT FROM AUTHOR]

The paper deals with a method of solution of a nonlinear integro-differential static string equation. The accuracy of the method is discussed. The numerical examples are given. [ABSTRACT FROM AUTHOR]

This paper deals with the numerical solution of time fractional diffusion equation. In this work, we consider the fractional derivative in the sense of Riemann-Liouville. At first, the time fractional derivative is discretized by integrating both sides of the equation with respect to the time variable and we arrive at a semi-discrete scheme. The stability and convergence of time discretized scheme are proven by using the energy method. Also we show that the convergence order of this scheme is O(τ2−α). Then we use the sinc collocation method to approximate the solution of semi-discrete scheme and show that the problem is reduced to a Sylvester matrix equation. Besides by performing some theorems, the exponential convergence rate of sinc method is illustrated. The numerical experiments are presented to show the excellent behavior and high accuracy of the proposed hybrid method in comparison with some other well known methods. [ABSTRACT FROM AUTHOR]

In this paper, two kinds of novel algorithms based on generalized Laguerre approximation with negative integer are presented to solve the delay differential equations. The algorithms differ from the spectral collocation method by the high sparsity of the matrices. Moreover, the use of generalized Laguerre polynomials leads to much simplified analysis and more precise error estimates. The numerical results indicate the high accuracy and the stability of long-time calculation of suggested algorithm. [ABSTRACT FROM AUTHOR]

In this paper we present a new algorithm for solving polynomial equations based on the Taylor series of the inverse function of a polynomial, f( y). The foundations of the computing of such series have been previously developed by the authors in some recent papers, proceeding as follows: given a polynomial function $y=P(x)=a_0+a_1x+\cdots+a_mx^m$, with $a_i \in \mathcal{R}, 0 \leq i \leq m$, and a real number u so that P′( u) ≠ 0, we have got an analytic function f( y) that satisfies x = f( P( x)) around x = u. Besides, we also introduce a new proof (completely different) of the theorems involves in the construction of f( y), which provide a better radius of convergence of its Taylor series, and a more general perspective that could allow its application to other kinds of equations, not only polynomials. Finally, we illustrate with some examples how f( y) could be used for solving polynomial systems. This question has been already treated by the authors in preceding works in a very complex and hard way, that we want to overcome by using the introduced algorithm in this paper. [ABSTRACT FROM AUTHOR]

Several methods have been proposed to calculate a rigorous error bound of an approximate solution of a linear system by floating-point arithmetic. These methods are called 'verification methods'. Applicable range of these methods are different. It depends mainly on the condition number and the dimension of the coefficient matrix whether such methods succeed to work or not. In general, however, the condition number is not known in advance. If the dimension or the condition number is large to some extent, then Oishi-Rump's method, which is known as the fastest verification method for this purpose, may fail. There are more robust verification methods whose computational cost is larger than the Oishi-Rump's one. It is not so efficient to apply such robust methods to well-conditioned problems. The aim of this paper is to choose a suitable verification method whose computational cost is minimum to succeed. First in this paper, four fast verification methods for linear systems are briefly reviewed. Next, a compromise method between Oishi-Rump's and Ogita-Oishi's one is developed. Then, an algorithm which automatically and efficiently chooses an appropriate verification method from five verification methods is proposed. The proposed algorithm does as much work as necessary to calculate error bounds of approximate solutions of linear systems. Finally, numerical results are presented. [ABSTRACT FROM AUTHOR]

In this paper, Homotopy Analysis Method (HAM) is applied to numerically approximate the eigenvalues of the fractional Sturm-Liouville problems. The eigenvalues are not unique. These multiple solutions, i.e., eigenvalues, can be calculated by starting the HAM algorithm with one and the same initial guess and linear operator $\mathcal{L}$. It can be seen in this paper that the auxiliary parameter $\hbar,$ which controls the convergence of the HAM approximate series solutions, has another important application. This important application is predicting and calculating multiple solutions. [ABSTRACT FROM AUTHOR]

Abstract  This paper sketches a technique for improving the rate of convergence of a general oscillatory sequence, and then applies this series acceleration algorithm to the polylogarithm and the Hurwitz zeta function. As such, it may be taken as an extension of the techniques given by Borwein’s “An efficient algorithm for computing the Riemann zeta function” by Borwein for computing the Riemann zeta function, to more general series. The algorithm provides a rapid means of evaluating Li s (z) for general values of complex s and a kidney-shaped region of complex z values given by ∣z 2/(z–1)∣z-plane, and so the algorithms described here allow for the evaluation of the polylogarithm for all complex s and z values. Alternatively, the Hurwitz zeta can be very rapidly evaluated by means of an Euler–Maclaurin series. The polylogarithm and the Hurwitz zeta are related, in that two evaluations of the one can be used to obtain a value of the other; thus, either algorithm can be used to evaluate either function. The Euler–Maclaurin series is a clear performance winner for the Hurwitz zeta, while the Borwein algorithm is superior for evaluating the polylogarithm in the kidney-shaped region. Both algorithms are superior to the simple Taylor’s series or direct summation. The primary, concrete result of this paper is an algorithm allows the exploration of the Hurwitz zeta in the critical strip, where fast algorithms are otherwise unavailable. A discussion of the monodromy group of the polylogarithm is included. [ABSTRACT FROM AUTHOR]

In this paper, a method is developed for solving nonsmooth nonconvex minimization problems. This method extends the classical BFGS framework. First, we generalize the Wolfe conditions for locally Lipschitz functions and prove that this generalization is well defined. Then, a line search algorithm is presented to find a step length satisfying the generalized Wolfe conditions. Next, the Goldstein e-subgradient is approximated by an iterative method and a descent direction is computed using a positive definite matrix. This matrix is updated using the BFGS method. Finally, a minimization algorithm based on the BFGS method is described. The algorithm is implemented in MATLAB and numerical results using it are reported. [ABSTRACT FROM AUTHOR]

Mathematical scripting languages are commonly used to develop new tomographic reconstruction algorithms. For large experimental datasets, high performance parallel (GPU) implementations are essential, requiring a re-implementation of the algorithm using a language that is closer to the computing hardware. In this paper, we introduce a new MATLAB interface to the ASTRA toolbox, a high performance toolbox for building tomographic reconstruction algorithms. By exposing the ASTRA linear tomography operators through a standard MATLAB matrix syntax, existing and new reconstruction algorithms implemented in MATLAB can now be applied directly to large experimental datasets. This is achieved by using the Spot toolbox, which wraps external code for linear operations into MATLAB objects that can be used as matrices. We provide a series of examples that demonstrate how this Spot operator can be used in combination with existing algorithms implemented in MATLAB and how it can be used for rapid development of new algorithms, resulting in direct applicability to large-scale experimental datasets. [ABSTRACT FROM AUTHOR]

In order to solve large sparse linear complementarity problems on parallel multiprocessor systems, modulus-based synchronous two-stage multisplitting iteration methods based on two-stage multisplittings of the system matrices were constructed and investigated by Bai and Zhang (Numer. Algoritm. 62, 59-77 ). These iteration methods include the multisplitting relaxation methods such as Jacobi, Gauss-Seidel, SOR and AOR of the modulus type as special cases. In the same paper the convergence theory of these methods is developed, under the following assumptions: (i) the system matrix is an H-matrix and (ii) one acceleration parameter is greater than the other. Here we show that the second assumption can be avoided, thus enabling us to obtain an improved convergence area. The result is obtained using the similar technique proposed by Cvetković and Kostić (Numer. Linear Algebra Appl. 21, 534-539 ), and its usage is demonstrated by an example of the LCP. [ABSTRACT FROM AUTHOR]

Motivated by the Cadzow filtering in seismic data processing, this paper presents a fast SVD method for multilevel block Hankel matrices. A seismic data presented as a multidimensional array is first transformed into a two dimensional multilevel block Hankel (MBH) matrix. Then the Lanczos process is applied to reduce the MBH matrix into a bidiagonal or tridiagonal matrix. Finally, the SVD of the reduced matrix is computed using the twisted factorization method. To achieve high efficiency, we propose a novel fast MBH matrix-vector multiplication method for the Lanczos process. In comparison with existing fast Hankel matrix-vector multiplication methods, our method applies 1-D, instead of multidimensional, FFT and requires minimum storage. Moreover, a partial SVD is performed on the reduced matrix, since complete SVD is not required by the Caszow filtering. Our numerical experiments show that our fast MBH matrix-vector multiplication method significantly improves both the computational cost and storage requirement. Our fast MBH SVD algorithm is particularly efficient for large size multilevel block Hankel matrices. [ABSTRACT FROM AUTHOR]

In this paper we present non-separable two-dimensional multi-resolution algorithms based on Harten's cell average framework for multi-resolution which guarantee a priori prescribed quality in the reconstructed image, hence being suitable for applications where quality control is most important, yet performing economically in terms of storage and speed of computation. Moreover, after applying the algorithm the exact error between the original and the decoded images measured in the L discrete norm is known without being necessary to decode the image. [ABSTRACT FROM AUTHOR]

Matrix completion aims to recover an unknown low-rank or approximately low-rank matrix from a sampling set of its entries. It is shown that this problem can be solved via its tightest convex relaxation obtained by minimizing the nuclear norm instead of the rank function. Recent studies have also shown that some non-convex penalties like M minimization and weighted nuclear norm minimization algorithms are able to recover low-rank matrix in a more efficient way. In this paper, we propose a unified framework based on Difference of Convex functions (DC) programming and DC Algorithms (DCA), by which M minimization and weighted nuclear norm minimization algorithms can be obtained as special cases of the general framework. In addition, we give another non-convex penalty-exponential type penalty. We make some comparison between numerical tests of our algorithms and the state-of-the-art method APGL and NIHT on randomly generated matrices and real matrix completion problems, the results suggest that our methods are more effective and promising. Moreover, for the application on low-rank image recovery, these non-convex algorithms we proposed also perform well and the results are more satisfactory and reasonable. [ABSTRACT FROM AUTHOR]

We consider the problem of computing satisfactory pairs of solutions of the differential equation for Legendre functions of non-negative integer order μ and degree $-\frac 12+i\tau $, where τ is a non-negative real parameter. Solutions of this equation are the conical functions $\mbox{{P}}^{\mu }_{-\frac 12+i\tau }(x)$ and ${Q}^{\mu }_{-\frac 12+i\tau }(x)$, x>−1. An algorithm for computing a numerically satisfactory pair of solutions is already available when −1 < x < 1 (see Gil et al. SIAM J. Sci. Comput. 31(3):1716-1741, 2009, Comput. Phys. Commun. 183:794-799, 2012). In this paper, we present a stable computational scheme for a real valued numerically satisfactory companion of the function $\mbox{{P}}^{\mu }_{-\frac 12+i\tau }(x)$ for x>1, the function $\Re \left \{e^{-i\pi \mu } {{Q}}^{\mu }_{-\frac {1}{2}+i\tau }(x) \right \}$. The proposed algorithm allows the computation of the function on a large parameter domain without requiring the use of extended precision arithmetic. [ABSTRACT FROM AUTHOR]

This paper proposes a fast algorithm for computing the discrete fractional Hadamard transform for the input vector of length N, being a power of two. A direct calculation of the discrete fractional Hadamard transform requires N real multiplications, while in our algorithm the number of real multiplications is reduced to N log N. [ABSTRACT FROM AUTHOR]

In the present paper we introduce new matrix extrapolation methods as generalizations of well known methods such as polynomial vector extrapolation methods or 휖-type algorithms. We give expressions of the obtained approximations via the Schur complement, the Kronecker product and also by using a new matrix product. We apply these methods to linearly generated sequences especially those arising in control or in ill-posed problems. [ABSTRACT FROM AUTHOR]

In this paper we give explicit expressions for the norms of the residual vectors generated by the GMRES algorithm applied to a non-normal matrix. They involve the right-hand side of the linear system, the eigenvalues, the eigenvectors and, in the non-diagonalizable case, the principal vectors. They give a complete description of how eigenvalues contribute in forming residual norms and offer insight in what quantities can prevent GMRES from being governed by eigenvalues. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new model for MR image reconstruction based on second order total variation ( $\text {TV}^{2}$) regularization and wavelet, which can be considered as requiring the image to be sparse in both the spatial finite differences and wavelet transforms. Furthermore, by applying the variable splitting technique twice, augmented Lagrangian method and the Barzilai-Borwein step size selection scheme, an ADMM algorithm is designed to solve the proposed model. It reduces the reconstruction problem to several unconstrained minimization subproblems, which can be solved by shrinking operators and alternating minimization algorithms. The proposed algorithm needs not to solve a fourth-order PDE but to solve several second-order PDEs so as to improve calculation efficiency. Numerical results demonstrate the effectiveness of the presented algorithm and illustrate that the proposed model outperforms some reconstruction models in the quality of reconstructed images. [ABSTRACT FROM AUTHOR]

In this paper, we consider an optimal control problem of switched systems with continuous-time inequality constraints. Because of the complexity of such constraints and switching laws, it is difficult to solve this problem by standard optimization techniques. To overcome the difficulty, we adopt a bi-level algorithm to divide the problem into two nonlinear constrained optimization problems: one continuous and the other discrete. To solve the problem, we transform the inequality constraints into equality constraints which is smoothed using a twice continuously differentiable function and treated as a penalty function. On this basis, the smoothed problem can be solved by any second-order gradient algorithm, e.g., Newton's Method. Finally, numerical examples show that our method is effective compared to existing algorithms. [ABSTRACT FROM AUTHOR]

We consider the task of computing solutions of linear systems that only differ by a shift with the identity matrix as well as linear systems with several different right-hand sides. In the past, Krylov subspace methods have been developed which exploit either the need for solutions to multiple right-hand sides (e.g. deflation type methods and block methods) or multiple shifts (e.g. shifted CG) with some success. In this paper we present a block Krylov subspace method which, based on a block Lanczos process, exploits both features-shifts and multiple right-hand sides-at once. Such situations arise, for example, in lattice quantum chromodynamics (QCD) simulations within the Rational Hybrid Monte Carlo (RHMC) algorithm. We present numerical evidence that our method is superior compared to applying other iterative methods to each of the systems individually as well as, in typical situations, to shifted or block Krylov subspace methods. [ABSTRACT FROM AUTHOR]

In this paper, we investigate variants of the well-known Golub and Welsch algorithm for computing nodes and weights of Gaussian quadrature rules for symmetric weights w in intervals (− a, a) (not necessarily bounded). The purpose is to reduce the complexity of the Jacobi eigenvalue problem stemming from Wilf's theorem and show the effectiveness of Matlab implementations of our variants for reducing the computer times compared to some other methods. Numerical examples on three test problems show the benefits of these variants. [ABSTRACT FROM AUTHOR]

In this paper, a new filled function method for finding a global minimizer of global optimization is proposed. The proposed filled function is continuously differentiable and only contains one parameter. It has no parameter sensitive terms. As a result, a general classical local optimization method can be used to find a better minimizer of the proposed filled function with easy parameter adjustment. Numerical experiments show that the proposed filled function method is effective. [ABSTRACT FROM AUTHOR]

The limited memory BFGS method (L-BFGS) is an adaptation of the BFGS method for large-scale unconstrained optimization. However, The L-BFGS method need not converge for nonconvex objective functions and it is inefficient on highly ill-conditioned problems. In this paper, we proposed a regularization strategy on the L-BFGS method, where the used regularization parameter may play a compensation role in some sense when the condition number of Hessian approximation tends to become ill-conditioned. Then we proposed a regularized L-BFGS method and established its global convergence even when the objective function is nonconvex. Numerical results show that the proposed method is efficient. [ABSTRACT FROM AUTHOR]

This paper presents a modified ODE-based algorithm for unconstrained optimization problems. It combines the idea of IMPBOT algorithm with nonmonotone and subspace techniques. The main feature of this method is that at each iteration, a lower dimensional system of linear equations is solved to obtain a trial step. Under some standard assumptions, the method is proven to be globally convergent. Numerical results show the efficiency of this proposed method in practical computation. [ABSTRACT FROM AUTHOR]

The gradient sampling (GS) algorithm for minimizing a nonconvex, nonsmooth function was proposed by Burke et al. (SIAM J Optim 15:751-779, ), whose most interesting feature is the use of randomly sampled gradients instead of subgradients. In this paper, combining the GS technique with the sequential quadratic programming (SQP) method, we present a feasible SQP-GS algorithm that extends the GS algorithm to nonconvex, nonsmooth constrained optimization. The proposed algorithm generates a sequence of feasible iterates, and guarantees that the objective function is monotonically decreasing. Global convergence is proved in the sense that, with probability one, every cluster point of the iterative sequence is stationary for the improvement function. Finally, some preliminary numerical results show that the proposed algorithm is effective. [ABSTRACT FROM AUTHOR]

The Bernstein operators of second kind were introduced by Paolo Soardi in 1990, in terms of a random walk on a certain hypergroup. They have the same relation with Chebyshev polynomials of second kind as the classical Bernstein operators have with Chebyshev polynomials of first kind. In this paper we describe a de Casteljau type algorithm for these operators. [ABSTRACT FROM AUTHOR]

In this paper, an efficient algorithm is presented for minimizing $\|A_1X_1B_1 + A_2X_2B_2+\cdots +A_lX_lB_l-C\|$ where $\|\cdot \|$ is the Frobenius norm, $X_i\in R^{n_i \times n_i}(i=1,2,\cdots ,l)$ is a reflexive matrix with a specified central principal submatrix $[x_{ij}]_{r\leq i,j\leq n_i-r}$. The algorithm produces suitable $[X_1,X_2,\cdots ,X_l]$ such that $\|A_1X_1B_1+A_2X_2B_2+\cdots +A_lX_lB_l-C\|=\min $ within finite iteration steps in the absence of roundoff errors. We show that the algorithm is stable any case. The algorithm requires little storage capacity. Given numerical examples show that the algorithm is efficient. [ABSTRACT FROM AUTHOR]

In this paper, a new nonmonotone inexact line search rule is proposed and applied to the trust region method for unconstrained optimization problems. In our line search rule, the current nonmonotone term is a convex combination of the previous nonmonotone term and the current objective function value, instead of the current objective function value . We can obtain a larger stepsize in each line search procedure and possess nonmonotonicity when incorporating the nonmonotone term into the trust region method. Unlike the traditional trust region method, the algorithm avoids resolving the subproblem if a trial step is not accepted. Under suitable conditions, global convergence is established. Numerical results show that the new method is effective for solving unconstrained optimization problems. [ABSTRACT FROM AUTHOR]

Affine arithmetic produces guaranteed enclosures for computed quantities, taking into account any uncertainties in the input data as well as round-off errors. Elementary operations on affine forms are redefined so they result in affine forms. Affine-linear operations result straightforwardly in affine forms. Non-linear operators, such as multiplication, must be approximated by affine forms. Choosing the appropriate approximation is a big challenge. The reason is that different approximations may be more accurate for specific purposes. This paper presents an efficient method for computing the minimum range (min-range) affine approximation of the product of arbitrary affine forms that do not contain zero properly. Numerical experiments are carried out to demonstrate the essential features of the proposed approach, especially its usefulness for bounding ranges of functions for global optimisation and for finding roots of functions. [ABSTRACT FROM AUTHOR]

Most of the methods for convergence acceleration of continued fractions K( a/ b) are based on the use of modified approximants S( ω) in place of the classical ones S(0), where ω are close to the tails f of the continued fraction. Recently (Nowak, Numer Algorithms 41(3):297-317, ), the author proposed an iterative method producing tail approximations whose asymptotic expansion accuracies are being improved in each step. This method can be successfully applied to a convergent continued fraction K( a/ b), where $a_m = \alpha_{-2} m^2 + \alpha_{-1} m + \ldots$, b = β m + β + ... ( α ≠ 0, $|\beta_{-1}|^2+|\beta_{0}|^2\neq 0$, i.e. $\deg a_m=2$, $\deg b_m\in\{0,1\}$). The purpose of this paper is to extend this idea to the class of two-variant continued fractions K ( a/ b + a′/ b′) with a, a′, b, b′ being rational in n and $\deg a_n=\deg a_n'$, $\deg b_n=\deg b_n'$. We give examples involving continued fraction expansions of some elementary and special mathematical functions. [ABSTRACT FROM AUTHOR]

In this paper, making use a exponential integral filter, a new algorithm for unconstrained global optimization is proposed. Compared with Yang's absolute value type integral filter method (Yang et al., Appl Math Comput 18:173-180, ), this algorithm is more effective and more sensitive. Numerical results for some typical examples show that in most cases, this algorithm works effectively and reliably. [ABSTRACT FROM AUTHOR]

In this paper an interior-point algorithm for P( κ) horizontal linear complementarity problems is proposed that uses new search directions. The theoretical complexity of the new algorithm is calculated. It is investigated that the proposed algorithm has quadratically convergent with polynomial iteration complexity $O((1+\kappa)\sqrt{n}\log\frac{n}{\varepsilon})$, coincide with the best known iteration bound for P( κ) horizontal linear complementarity problems. [ABSTRACT FROM AUTHOR]

In this paper, by using a special matrix factorization, a symbolic computational algorithm is developed to solve the cyclic penta-diagonal linear system. The algorithm is suitable for implementation using Computer Algebra Systems (CASs) such as MATLAB, MATHEMATICA and MAPLE. In addition, an efficient way of evaluating the determinant of a cyclic penta-diagonal matrix is also discussed. Two numerical examples are given for the purpose of illustration. [ABSTRACT FROM AUTHOR]

This paper is concerned with a three-level alternating direction implicit (ADI) method for the numerical solution of a 3D hyperbolic equation. Stability criterion of this ADI method is given by using von Neumann method. Meanwhile, it is shown by a discrete energy method that it can achieve fourth-order accuracy in both time and space with respect to H- and L-norms only if stable condition is satisfied. It only needs solution of a tri-diagonal system at each time step, which can be solved by multiple applications of one-dimensional tri-diagonal algorithm. Numerical experiments confirming the high accuracy and efficiency of the new algorithm are provided. [ABSTRACT FROM AUTHOR]

In this paper we propose a method for computing the roots of a monic matrix polynomial. To this end we compute the eigenvalues of the corresponding block companion matrix C. This is done by implementing the QR algorithm in such a way that it exploits the rank structure of the matrix. Because of this structure, we can represent the matrix in Givens-weight representation. A similar method as in Chandrasekaran et al. (Oper Theory Adv Appl 179:111-143, ), the bulge chasing, is used during the QR iteration. For practical usage, matrix C has to be brought in Hessenberg form before the QR iteration starts. During the QR iteration and the transformation to Hessenberg form, the property of the matrix being unitary plus low rank numerically deteriorates. A method to restore this property is used. [ABSTRACT FROM AUTHOR]

In this paper, we develop a fourth order method for solving the systems of nonlinear equations. The algorithm is composed of two weighted-Newton steps and requires the information of one function and two first Fréchet derivatives. Therefore, for a system of n equations, per iteration it uses n + 2 n evaluations. Computational efficiency is compared with Newton's method and some other recently published methods. Numerical tests are performed, which confirm the theoretical results. From the comparison with known methods it is observed that present method shows good stability and robustness. [ABSTRACT FROM AUTHOR]