Search

Despite the success of stochastic variance-reduced gradient (SVRG) algorithms in solving large-scale problems, their stochastic gradient complexity often scales linearly with data size and is expensive for huge data. Accordingly, we propose a hybrid stochastic-deterministic minibatch proximal gradient~(HSDMPG) algorithm for strongly convex problems with linear prediction structure, e.g.~least squares and logistic/softmax regression. HSDMPG~enjoys improved computational complexity that is data-size-independent for large-scale problems. It iteratively samples an evolving~minibatch of individual losses to estimate the original problem, and efficiently minimizes the sampled smaller-sized subproblems. For strongly convex loss of n components, HSDMPG~attains an $\epsilon$ -optimization-error within $\mathcal{O} \left(\kappa\log^{\zeta+1}\left(\frac{1}{\epsilon}\right)\frac{1}{\epsilon}\bigwedge n\log^{\zeta}\left(\frac{1}{\epsilon}\right)\right)$ stochastic gradient evaluations, where $\kappa$ is condition number, $\zeta=1$ for quadratic loss and $\zeta=2$ for generic loss. For large-scale problems, our complexity outperforms those of SVRG-type algorithms with/without dependence on data size. Particularly, when $\epsilon=\mathcal{O}(1/\sqrt{n})$ which matches the intrinsic excess error of a learning model and is sufficient for generalization, our complexity for quadratic and generic losses is respectively $\mathcal{O} (n^{0.5}\log^{2}(n))$ and $\mathcal{O} (n^{0.5}\log^{3}(n))$ , which for the first time achieves optimal generalization in less than a single pass over data. Besides, we extend HSDMPG~to online strongly convex problems and prove its higher efficiency over the prior algorithms. Numerical results demonstrate the computational advantages of~HSDMPG.

Formulations of an extra-degree-of-freedom (DOF) free extended isogeometric analysis (IGA) are presented in this study. The idea is achieved by reconstruction of the coefficients through a mesh-free-based local approximation, based on the framework of a generalized finite-element method. The enrichment functions are embedded in the mesh-free basis implicitly, resulting in an identical number of DOFs. Moreover, the system condition number is of the same level between the enriched IGA and non-enriched version. The approach to handling the blending issues is discussed. Numerical examples with a solution containing sharp features/singularities are designed and studied in terms of accuracy and convergence.

The radial basis function interpolation is an effective method for approximation on scattered data. However, this interpolation method suffers from the contradiction between the accuracy and the numerical stability. With considering the distribution of the interpolation points, a bounded random shape variation scheme for the radial basis function is developed to circumvent the problem of numerical stability. In this scheme, the shape variation is bounded by the value that is determined by the maximum distance and the minimal distance which are applied to describe the average density of the interpolation centers. Within this bound, the shape of the MQ is modified through a random scheme. With applying this bounded randomly variable shape scheme, the accuracy and the stability of the MQ interpolation are balanced. Comparisons on the accuracy and the condition number of the interpolation matrix between the constant shaped MQ interpolation and this bounded randomly variable shaped MQ interpolation have been made to verify the conclusion. Furthermore, this scheme is integrated in the dual reciprocity boundary element method in the analysis of three dimensional elastic problems. Results of the numerical examples demonstrated that the developed scheme improved the accuracy of the dual reciprocity boundary element method stably.

In this paper, the robust minimum norm partial eigenstructure assignment problems (PESAPs) are studied in a singular vibrating structure via acceleration-velocity-displacement active control. The solvability and stabilization conditions are given by using the singular value decomposition method and no spill-over property of eigenvalues and corresponding eigenvectors. A new parametric method is proposed for solving the PESAPs using the imposed modal constraints technique. Based on the derived condition number of closed-loop eigenvalues, the robust and minimum norm PESAPs are considered by setting appropriate weight factors. Algorithms are presented for solving the corresponding problems. Two numerical examples are reported to verify the effectiveness of algorithms.

The original solutions of highly oscillatory integral equations usually have rapid oscillation, which means that conventional numerical approaches used to solve these equations have poor convergence. In order to overcome this difficulty, in this paper, we propose and analyze an oscillation-preserving Legendre-Galerkin method for second kind integral equations with highly oscillatory kernels. Concretely, we first incorporate the standard approximation subspace of Legendre polynomial basis with a finite number of oscillatory functions which capture the oscillation of the exact solutions. Then, we construct an efficient numerical integration scheme, yielding a fully discrete linear system. Making use of best approximation results for some weighted projection operators defined in suitable weighted Sobolev spaces and the compactness operator theory, we establish that the fully discrete approximate equation has a unique solution and the approximate solution reaches an optimal convergence order without the influence of the wave number. In addition, we prove that for sufficiently large wave number, the spectral condition number of the corresponding linear system is uniformly bounded. At last, we use numerical examples to demonstrate the effectiveness of the proposed method.

Gradient method is a simple optimization approach using minus gradient of the objective function as a search direction. Its efficiency highly relies on the choices of the stepsize. In this paper, the convergence behavior of a class of gradient methods, where the stepsize has an important property introduced in (Dai in Optimization 52:395–415, 2003), is analyzed. Our analysis is focused on minimization on strictly convex quadratic functions. We establish the R-linear convergence and derive an estimate for the R-factor. Specifically, if the stepsize can be expressed as a collection of Rayleigh quotient of the inverse Hessian matrix, we are able to show that these methods converge R-linearly and their R-factors are bounded above by $$1-\frac{1}{\varkappa }$$ , where $$\varkappa$$ is the associated condition number. Preliminary numerical results demonstrate the tightness of our estimate of the R-factor.

In this article, a hybrid Haar wavelet collocation method (HWCM) is proposed for the ill-posed inverse problem with unknown source control parameters. Applying numerical techniques to such problems is a challenging task due to the presence of nonlinear terms, unknown control parameter sources along the solution inside the given region. To find the numerical solution, derivatives are discretized adopting implicit finite-difference scheme and Haar wavelets. The computational stability and theoretical rate of convergence of the proposed HWCM are discussed in detail. Two numerical experiments are incorporated to show the well-condition behavior of the matrix obtained from HWCM and hence not required to supplement some regularization procedures. Moreover, the numerical solutions of the considered experiments illustrate the reliability, suitability, and correctness of HWCM.

Let us consider the non-local problem − L α u = f , α ∈ ( 0 , 1 ) , L is a second order self-adjoint elliptic operator in Ω ⊂ R d with Neumann boundary conditions on ∂ Ω . The problem is discretized by finite difference or finite element method, thus obtaining the linear system A α u = f , A is sparse symmetric and positive semidefinite matrix. The proposed method is based on best uniform rational approximations (BURA) of degree k , r α , k , of the scalar function t α , t ∈ [ 0 , 1 ] . Then, the approximate solution u r of the fractional power linear system is defined as u ≈ u r = λ 2 − α r α , k ( λ 2 A † ) f , where λ 2 is the first positive eigenvalue of A , and A † stands for the Moore–Penrose pseudo inverse of A . The BURA method reduces the non-local problem to solution of k linear systems with matrices A + d i I , d i > 0 , i = 1 , … , k . An exponential convergence rate with respect to k is proven. The error estimates are robust with respect to the condition number of A in the subspace orthogonal to the constant vectors. The algorithm has almost optimal computational complexity assuming that optimal iterative solvers are applied to the auxiliary sparse linear systems. The first group of numerical tests illustrates in detail the obtained theoretical results. Finite difference discretization of a model 2D problem is used for this purpose. The second part of numerical tests demonstrates the applicability of BURA methods for 3D problems in domains with general geometry. Linear finite elements on unstructured tetrahedral meshes with local mesh refinement are used in the presented large-scale experiments, confirming also the almost optimal computational complexity.

This paper develops an efficient local meshless collocation algorithm for approximating the time fractional evolution model that is applied for the modeling of heat flow in materials with memory. The model is based on the Riemann-Liouville fractional integral. The proposed method discretizes the unknown solution using two main parts. First, the temporal direction is approximated through the second-order finite difference scheme. Second, the spatial direction of the governing problem is discretized via the local radial basis function partition of unity technique. The major drawback of global collocation techniques is the computational cost associated with arisen dense algebraic system. This localized method is based on partitioning the original domain to several subdomains by means of the kernel approximation on each local domain and allows one to significantly sparsify the algebraic system having small condition number in addition to lowering the computational cost. The stability and convergence of the time difference formulation are discussed in detail with respect to the H 1 -norm. Numerical results and comparisons are illustrated in order to confirm theoretical analysis and the accuracy of the method.

We present a combination of two algorithms that accurately calculate multiple roots of general polynomials. Algorithm I transforms the singular root-finding into a regular nonlinear least squares problem on a pejorative manifold, and calculates multiple roots simultaneously from a given multiplicity structure and initial root approximations. To fulfill the input requirement of Algorithm I, we develop a numerical GCD-finder containing a successive singular value updating and an iterative GCD refinement as the main engine of Algorithm II that calculates the multiplicity structure and the initial root approximation. While limitations of our algorithm exist in identifying the multiplicity structure in certain situations, the combined method calculates multiple roots with high accuracy and consistency in practice without using multiprecision arithmetic even if the coefficients are inexact. This is perhaps the first blackbox-type root-finder with such capabilities. To measure the sensitivity of the multiple roots, a structure-preserving condition number is proposed and error bounds are established. According to our computational experiments and error analysis, a polynomial being ill-conditioned in the conventional sense can be well conditioned with the multiplicity structure being preserved, and its multiple roots can be computed with high accuracy.

Highly oscillatory integrals are frequently involved in applied problems, particularly for large-scale data and high frequencies. Levin method with global radial basis functions was implemented for numerical evaluation of these integrals in the literature. However, when the frequency is large or nodal points are increased, the Levin method with global radial basis functions faces several issues such as large condition number of the interpolation matrix and computationally inefficiency of the method, etc. In this paper, the Levin method with compactly supported radial basis functions is proposed to handle deficiencies of the method. In addition, theoretical error bounds and stability analysis of the proposed methods are performed. Several numerical examples are included to verify the accuracy, efficiency, and well-conditioned behavior of the proposed methods.

In this study, an iterative algorithm is proposed to solve the nonlinear matrix equation $$X+A^{*}{e}^{X}A=I_{n}$$ . Explicit expressions for mixed and componentwise condition numbers with their upper bounds are derived to measure the sensitivity of the considered nonlinear matrix equation. Comparative analysis for the derived condition numbers and the proposed algorithm are presented. The proposed iterative algorithm reduces the number of iterations significantly when incorporated with exact line searches. Componentwise condition number seems more reliable to detect the sensitivity of the considered equation than mixed condition number as validated by numerical examples.

In 1993, Shub and Smale posed the problem of finding a sequence of univariate polynomials of degree $N$ with condition number bounded above by $N$. In a previous paper by C. Belt\'an, U. Etayo, J. Marzo and J. Ortega-Cerd\`a, it was proved that the optimal value of the condition number is of the form $O(\sqrt{N})$, and the sequence demanded by Shub and Smale was described by a closed formula (for large enough $N\geqslant N_0$ with $N_0$ unknown) and by a search algorithm for the rest of the cases. In this paper we find concrete estimates for the constant hidden in the $O(\sqrt{N})$ term and we describe a simple formula for a sequence of polynomials whose condition number is at most $N$, valid for all $N=4M^2$, with $M$ a positive integer., Comment: 21 pages

The doubly stochastic functional gradient descent algorithm (DSG) that is memory friendly and computationally efficient can effectively scale up kernel methods. However, in solving the highly ill-conditioned large-scale nonlinear machine learning problem, the convergence speed of DSG is quite slow. This is because the condition number of the Hessian matrix of this problem is quite large, which will make stochastic gradient methods converge very slowly. Fortunately, gradient preconditioning is a well-established technique in optimization aiming to reduce the condition number. Therefore, we propose a preconditioned doubly stochastic functional gradient descent algorithm (P-DSG) by combining DSG with gradient preconditioning. P-DSG first uses the gradient preconditioning to adaptively scale the individual components of the estimated functional gradient obtained by DSG, and then utilizes the preconditioned functional gradient as the descent direction in each iteration. Theoretically, an appropriate preconditioner is always the inverse of the Hessian matrix at the optimum, which is not easy to get due to its high computation cost. Therefore, we first choose an empirical covariance matrix of random Fourier features to approximate the Hessian matrix, and then perform a low-rank approximation to the empirical covariance matrix. P-DSG has a fast convergence rate $\mathcal {O}(1/t)$ and produces a smaller constant factor in the boundary than that of DSG while remains $\mathcal {O}(t)$ memory friendly and $\mathcal {O}(td)$ computationally efficient. Finally, we test the performance of P-DSG on the kernel ridge regression, kernel support vector machines, and kernel logistic regression, respectively. The experimental results show that P-DSG speeds up convergence and achieves better performance.

There has been much research about regularizing optimal portfolio selections through $$\ell _1$$ norm and/or $$\ell _2$$ -norm squared. The common consensuses are (i) $$\ell _1$$ leads to sparse portfolios and there exists a theoretical bound that limits extreme shorting of assets; (ii) $$\ell _2$$ (norm-squared) stabilizes the computation by improving the condition number of the problem resulting in strong out-of-sample performance; and (iii) there exist efficient numerical algorithms for those regularized portfolios with closed-form solutions each step. When combined such as in the well-known elastic net regularization, theoretical bounds are difficult to derive so as to limit extreme shorting of assets. In this paper, we propose a minimum variance portfolio with the regularization of $$\ell _1$$ and $$\ell _2$$ norm combined (namely $$\ell _{1, 2}$$ -norm). The new regularization enjoys the best of the two regularizations of $$\ell _1$$ norm and $$\ell _2$$ -norm squared. In particular, we derive a theoretical bound that limits short-sells and develop a closed-form formula for the proximal term of the $$\ell _{1,2}$$ norm. A fast proximal augmented Lagrange method is applied to solve the $$\ell _{1,2}$$ -norm regularized problem. Extensive numerical experiments confirm that the new model often results in high Sharpe ratio, low turnover and small amount of short sells when compared with several existing models on six datasets.

This paper is concerned with the squared F(robenius)-norm regularized factorization form for noisy low-rank matrix recovery problems. Under a suitable assumption on the restricted condition number of the Hessian matrix of the loss function, we establish an error bound to the true matrix for the non-strict critical points with rank not more than that of the true matrix. Then, for the squared F-norm regularized factorized least squares loss function, we establish its KL property of exponent 1/2 on the global optimal solution set under the noisy and full sample setting, and achieve this property at its certain class of critical points under the noisy and partial sample setting. These theoretical findings are also confirmed by solving the squared F-norm regularized factorization problem with an accelerated alternating minimization method.

A meshless numerical scheme, named as space-time backward substitution method (STBSM), is proposed for 3D unsteady advection-diffusion equations (ADEs). In this method, the numerical solution is composed by approximation of boundary points and approximation of internal domain. Here, the space-time radial basis function (STRBF) is applied to construct internal approximation which satisfies homogeneous boundary condition. While, time dimension, as a new variable in radial coordinate, is incorporated into the global space-time basis function. Different from using other common global basis functions, the STBSM with STRBF does not require the temporal discretization, which makes it easy-to program and time saving. In addition, compactly supported space-time radial basis function (CS-STRBF) is introduced to reduce the original resultant full matrix to a sparse matrix, compared with global space-time radial basis function. It can overcome ill-conditioned matrix caused by an excessive condition number. Numerical results of two examples show that the proposed method provides accurate and stable solutions with low computational cost for three dimensional advection-diffusion equations. Moreover, comparison results indicate that the accuracy of the method is 2 − 4 orders of magnitude higher than the dimension splitting element-free Galerkin (DSEFG) [19] algorithm with less time expense.

The multinode Shepard operator is a linear combination of local polynomial interpolants with inverse distance weighting basis functions. This operator can be rewritten as a blend of function values with cardinal basis functions, which are a combination of the inverse distance weighting basis functions with multivariate Lagrange fundamental polynomials. The key for simply computing the latter, on a unisolvent set of points, is to use a translation of the canonical polynomial basis and the P A = L U factorization of the associated Vandermonde matrix. In this paper, we propose a method to numerically solve a Poisson equation with Dirichlet conditions through multinode Shepard interpolants by collocation. This collocation method gives rise to a collocation matrix with many zero entrances and a smaller condition number with respect to the one of the well known Kansa method. Numerical experiments show the accuracy and the performance of the proposed collocation method.

The discrete unified gas kinetic scheme (DUGKS) combines the advantages of both the unified gas kinetic scheme (UGKS) and the lattice Boltzmann method. It can adopt the flexible meshes, meanwhile, the flux calculation is simple. However, the original DUGKS is proposed for the compressible flows. When we try to solve a problem governed by the incompressible Navier-Stokes (N-S) equations, the original DUGKS may bring some undesirable errors because of the compressible effect. To eliminate the compressible effect, the DUGKS for incompressible N-S equations is developed in this work. In addition, the Chapman-Enskog analysis ensures that the present DUGKS can solve the incompressible N-S equations exactly, meanwhile, a new non-extrapolation scheme is adopted to treat the Dirichlet boundary conditions. To test the present DUGKS for incompressible N-S equations, four problems are adopted. The first one is a periodic problem driven by an external force, which is used to test the influences of Courant–Friedrichs–Lewy condition number and the M a c h number (Ma). Besides, some comparisons between the present DUGKS and some available results are also conducted. The second problem is Womersley flow, it is also used to test the influence of Ma, and the results show that the compressible effect is reduced obviously. Then, the two-dimensional lid-driven cavity flow is considered. In these simulations, the Reynolds number is varied from 400 to 1000000 to illustrate the accuracy, stability and efficiency of the present DUGKS. Finally, the numerical solutions of the three-dimensional lid-driven cavity flow suggest that the present DUGKS is suitable for the three-dimensional problems.

A matrix $A\in\mathbb{C}^{n\times n}$ is diagonalizable if it has a basis of linearly independent eigenvectors. Since the set of nondiagonalizable matrices has measure zero, every $A\in \mathbb{C}^{n\times n}$ is the limit of diagonalizable matrices. We prove a quantitative version of this fact conjectured by E.B. Davies: for each $\delta\in (0,1)$, every matrix $A\in \mathbb{C}^{n\times n}$ is at least $\delta\|A\|$-close to one whose eigenvectors have condition number at worst $c_n/\delta$, for some constants $c_n$ dependent only on $n$. Our proof uses tools from random matrix theory to show that the pseudospectrum of $A$ can be regularized with the addition of a complex Gaussian perturbation. Along the way, we explain how a variant of a theorem of \'Sniady implies a conjecture of Sankar, Spielman and Teng on the optimal constant for smoothed analysis of condition numbers., Comment: 17pp. Fixed a mistake in the appendix, all results are unchanged. Accepted version, to appear in CPAM

The numerical solution of the electric field integral equation in electromagnetic scattering problems involving metallic bodies, using the method of moments in conjunction with the fast multipole method, gives rise a full matrix with highly spread complex eigenvalues and consequently with a low condition number. Thus, iterative methods may not converge or it will require an extremely large number of iterations, which make this strategy unfeasible due to the high solution time and the expensive computational resources required. To overcome this drawback, the system matrix must be preconditioned to ensure the convergence in a reasonable number of iterations and with appropriate accuracy. In this work, some preconditioning techniques are revised and applied to a linear equation system derived from such type of problems, and the performance of these preconditioners is estimated and analyzed comparatively using the generalized minimal residual iterative method.

Consider Laplace’s equation in a bounded simply-connected domain S, and use the method of fundamental solutions (MFS). The error and stability analysis is made for circular/elliptic pseudo-boundaries in Dou et al. (J. Comp. Appl. Math. 377:112861, 2020), and polynomial convergence rates and exponential growth rates of the condition number (Cond) are obtained. General pseudo-boundaries are suggested for more complicated solution domains in Dou et al. (J. Comp. Appl. Math. 377:112861, 2020, Section 5). Since the ill-conditioning is severe, the success in computation by the MFS mainly depends on stability. This paper is devoted to stability analysis for smooth closed pseudo-boundaries of source nodes. Bounds of the Cond are derived, and exponential growth rates are also obtained. This paper is the first time to explore stability analysis of the MFS for non-circular/non-elliptic pseudo-boundaries. Circulant matrices are often employed for stability analysis of the MFS; but the stability analysis in this paper is explored based on new techniques without using circulant matrices as in Dou et al. (J. Comp. Appl. Math. 377:112861, 2020). To pursue better pseudo-boundaries, the sensitivity index is proposed from growth/convergence rates of stability via accuracy. Better pseudo-boundaries in the MFS can be found by trial computations, to develop the study in Dou et al. (J. Comp. Appl. Math. 377:112861, 2020) for the selection of pseudo-boundaries. For highly smooth and singular solutions, better pseudo-boundaries are different; an analysis of the sensitivity index is explored. Circular/elliptic pseudo-boundaries are optimal for highly smooth solutions, but not for singular solutions. In this paper, amoeba-like domains are chosen in computation. Several useful types of pseudo-boundaries are developed and their algorithms are simple without using nonlinear solutions. For singular solutions, numerical comparisons are made for different pseudo-boundaries via the sensitivity index.

We consider the sensitivity of real zeros of structured polynomial systems to pertubations of their coefficients. In particular, we provide explicit estimates for condition numbers of structured random real polynomial systems and extend these estimates to the smoothed analysis setting.

We develop a generalization of Nesterov's accelerated gradient descent method which is designed to deal with orthogonality constraints. To demonstrate the effectiveness of our method, we perform numerical experiments which demonstrate that the number of iterations scales with the square root of the condition number, and also compare with existing state-of-the-art quasi-Newton methods on the Stiefel manifold. Our experiments show that our method outperforms existing state-of-the-art quasi-Newton methods on some large, ill-conditioned problems., 17 pages, 4 figures

We develop a nonoverlapping Additive Schwarz Preconditioner for the p-version finite element with $$H^2$$ -conforming elements on triangles based on Argyris elements. With a particular choice of basis functions corresponding to the $$C^2$$ degrees of freedom (dofs), we give a preconditioner consisting of eliminating the interior dofs, global solves of the $$C^0$$ and $$C^1$$ vertex dofs, diagonal solves of the $$C^2$$ vertex dofs, and block diagonal solves of the edge dofs. We show that the condition number of the preconditioner system grows at most like $${\mathscr {O}}(1+\log ^3 p)$$ independent of the mesh size h. The analysis permits the use of inexact interior solves which lends itself to a more efficient implementation while maintaining the same $${\mathscr {O}}(1 + \log ^3 p)$$ asymptotic growth of the preconditioned system.

The truncated singular value decomposition (TSVD) is a popular method for solving linear discrete ill-posed problems with a small to moderately sized matrix A. This method replaces the matrix A by the closest matrix A k of low rank k, and then computes the minimal norm solution of the linear system of equations with a rank-deficient matrix so obtained. The modified TSVD (MTSVD) method improves the TSVD method, by replacing A by a matrix that is closer to A than A k in a unitarily invariant matrix norm and has the same spectral condition number as A k . Approximations of the SVD of a large matrix A can be computed quite efficiently by using a randomized SVD (RSVD) method. This paper presents a novel modified truncated randomized singular value decomposition (MTRSVD) method for computing approximate solutions to large-scale linear discrete ill-posed problems. The rank, k, is determined with the aid of the discrepancy principle, but other techniques for selecting a suitable rank also can be used. Numerical examples illustrate the effectiveness of the proposed method and compare it to the truncated RSVD method.

We consider the problem of reconstructing a compactly supported function from samples of its Fourier transform taken along a spiral. We determine the Nyquist sampling rate in terms of the density of the spiral and show that, below this rate, spirals suffer from an approximate form of aliasing. This sets a limit to the amount of undersampling that compressible signals admit when sampled along spirals. More precisely, we derive a lower bound on the condition number for the reconstruction of functions of bounded variation, and for functions that are sparse in the Haar wavelet basis.

We develop a preconditioned fast divided-and-conquer finite element approximation for the initial-boundary value problem of variable-order time-fractional diffusion equations. Due to the impact of the time-dependent variable order, the coefficient matrix of the resulting all-at-once system does not have a Toeplitz-like structure. In this paper we derive a fast approximation of the coefficient matrix by the means of a sum of Toeplitz matrices multiplied by diagonal matrices. We show that the approximation is asymptotically consistent with the original problem, which requires O ( M N log 3 ⁡ N ) computational complexity and O ( M N log 2 ⁡ N ) memory with M and N being the numbers of degrees of freedom in space and time, respectively. Furthermore, a preconditioner is introduced to reduce the number of iterations caused by the bad condition number of the coefficient matrix. Numerical experiments are presented to demonstrate the effectiveness and the efficiency of the proposed method.

This paper proposes an effective gradient-descent iterative algorithm for solving a generalized Sylvester-transpose equation with rectangular matrix coefficients. The algorithm is applicable for the equation and its interesting special cases when the associated matrix has full column-rank. The main idea of the algorithm is to have a minimum error at each iteration. The algorithm produces a sequence of approximated solutions converging to either the unique solution, or the unique least-squares solution when the problem has no solution. The convergence analysis points out that the algorithm converges fast for a small condition number of the associated matrix. Numerical examples demonstrate the efficiency and effectiveness of the algorithm compared to renowned and recent iterative methods.

The modeling of thermodynamic equilibria leads to complex nonlinear chemical systems which are often solved with the Newton-Raphson method. But this resolution can lead to a non convergence or an excessive number of iterations due to the very ill-conditioned nature of the problem. In this work, we combine a particular formulation of the equilibrium system called the Positive Continuous Fraction method with two iterative methods, Anderson Acceleration method and Vector extrapolation methods (namely the reduced rank extrapolation and the minimal polynomial extrapolation). The main advantage of this approach is to avoid forming the Jacobian matrix. In addition, a strategy is used to improve the robustness of the Anderson acceleration method which consists in reducing the condition number of matrix of the least squares problem in the implementation of the Anderson acceleration so that the numerical stability can be guaranteed. We compare our numerical results with those obtained with the Newton-Raphson method on the Acid Gallic test and the 1D MoMas benchmark test case and we show the high efficiency of our approach.

In this paper, we consider diagonal-times-nonsymmetric-Toeplitz (DNT) preconditioner for Toeplitz-like linear systems arising from one-sided space fractional diffusion equations (OSFDE) with variable coefficients. We first correct the result of Lemma 3.3 in Lin et al. (BIT Numer Math 58, 729–748, 2018) and prove the corrected result. We then extend the DNT preconditioner to Toeplitz-like linear systems arising from OSFDEs, where high order difference operators are applied to discretize the fractional derivative. Theoretically, we prove that the condition number of the preconditioned matrix is uniformly bounded by a constant under mild assumptions and verify that several discretization schemes from the literature satisfy the required assumptions. Numerical results are reported to show the efficiency of the DNT preconditioner.

In this paper, we propose a robust framework based on the scaled boundary finite element method to model implicit interfaces in two-dimensional differential equations in nonhomegeneous media. The salient features of the proposed work are: (a) interfaces can be implicitly defined and need not conform to the background mesh; (b) Dirichlet boundary conditions can be imposed directly along the interface; (c) does not require special numerical integration technique to compute the bilinear and the linear forms and (d) can work with an efficient local mesh refinement using hierarchical background meshes. Numerical examples involving straight interface, circular interface and moving interface problems are solved to validate the proposed technique. Further, the presented technique is compared with conforming finite element method in terms of accuracy and convergence. From the numerical studies, it is seen that the proposed framework yields solutions whose error is O ( h 2 ) in L 2 norm and O ( h ) in the H 1 semi-norm. Further the condition number increases with the mesh size similar to the FEM.

When linearizing three-dimensional (3D) coordinate similarity transformation model with large rotations, we usually encounter the ill-posed normal matrix which may aggravate the instability of solutions. To alleviate the problem, a series of conversions are contributed to the 3D coordinate similarity transformation model in this paper. We deduced a complete solution for the 3D coordinate similarity transformation at any rotation with the nonlinear adjustment methodology, which involves the errors of the common and the non-common points. Furthermore, as the large condition number of the normal matrix resulted in an intractable form, we introduced the bary-centralization technique and a surrogate process for deterministic element of the normal matrix, and proved its benefit for alleviating the condition number. The experimental results show that our approach can obtain the smaller condition number to stabilize the convergence of the interested parameters. Especially, our approach can be implemented for considering the errors of the common and the non-common points, thus the accuracy of the transformed coordinates improves.

The goals of this paper are twofold: selection of pseudo-boundaries for sources nodes in the method of fundamental solutions (MFS), and comparisons of the MFS, the method of particular solutions (MPS) and the MFS-QR of Antunes. To pursue better pseudo-boundaries, we provide new estimates of the condition number (Cond) by the MFS for arbitrary pseudo-boundaries, and propose a new sensitivity index of stability via accuracy. Numerical experiments and comparisons are carried out to verify the analysis made. For five-pedal-flower-like domains, numerical comparisons are made by the sensitivity index. Circular pseudo-boundaries are optimal for highly smooth solutions, but the pseudo-boundaries near the domain boundary may be better for singular solutions. In this paper the gap has been shortened between theoretical analysis and numerical computation of the MFS, to provide some guidance for users. This is the first goal of this paper. The second goal is to compare the MFS, the MPS and the MFS-QR. Characteristics of the MFS-QR are explored. The new basis functions of the MFS-QR are the very particular solutions (PS), and the MFS-QR may be regarded as a special MPS. The MFS-QR is not a variant of the MFS but a variant of the MPS. The MFS-QR also plays a role in bridging from the MFS to the MPS. Both the MFS and the MPS can also be recognized as twins via the MFS-QR in the Trefftz family. The comparisons in this paper are more comprehensive.

To solve various problems in complicated and concave domains by the method of fundamental solutions (MFS), it is required to consider a large number of source and collocation points that increases the computational time of the analysis. This paper suggests a modification to the MFS, which can make it more efficient and reliable for solving applied problems in complicated domains. In the proposed method, each pseudo source is converted to two or more number of sub-sources with equal intensities. Therefore, the total number of sources is increased while the number of unknowns is not increased. By this approach we will be able to reduce the distance between the main and the pseudo boundaries and therefore modeling the problems with complicated boundaries can be performed effectively. The proposed method is investigated for a scalar field problem, i.e. the Laplace equation, and a vector field problem, i.e. elastostatic problem. It is shown that by using the proposed method, in addition to reducing the calculation time, the condition number of the coefficient matrix also significantly decreases. By solving several numerical example problems, it is observed that the presented method can obtain accurate solutions by using a small number of collocation points.

As one new result, for a symmetric Toeplitz $ \operatorname{sinc} $ $n \times n$-matrix $A(t)$ depending on a parameter $t$, lower estimates (tending to infinity as t vanishes) on the pertinent condition number are derived. A further important finding is that prior to improving the obtained lower estimates it seems to be more important to determine the lower bound on the parameter $t$ such that the smallest eigenvalue $\mu_n(t)$ of $A(t)$ can be reliably computed since this is a precondition for determining a reliable value for the condition number of the Toeplitz $ \operatorname{sinc} $ matrix. The style of the paper is expository in order to address a large readership.

The harmonic balance method has emerged as an efficient and accurate approach for computing periodic, as well as almost periodic, solutions to nonlinear ordinary differential equations. The accuracy of the harmonic balance method can however be negatively impacted by aliasing. Aliasing occurs because Fourier coefficients of nonlinear terms in the governing equations are approximated by a discrete Fourier transform (DFT). Understanding how aliasing occurs when the DFT is applied is therefore essential in improving the accuracy of the harmonic balance method. In this work, a new operator that describe the fold-back, i.e. aliasing, of unresolved frequencies onto the resolved ones is developed. The norm of this operator is then used as a metric for investigating how the time sampling should be performed to minimize aliasing. It is found that a time sampling which minimizes the condition number of the DFT matrix is the best choice in this regard, both for single and multiple frequency problems. These findings are also verified for the Duffing oscillator. Finally, a strategy for oversampling multiple frequency harmonic balance computations is developed and tested.

One of the attractive and practical techniques to transform the domain integrals to equivalent boundary integrals is the dual reciprocity method (DRM). The success of DRM relies on the proper treatment of the non-homogeneous term in the governing differential equation. For this purpose, radial basis functions (RBFs) interpolations are performed to approximate the non-homogeneous term accurately. Moreover, when the interpolation points are large, the global RBFs produced dense and ill-conditioned interpolation matrix, which poses severe stability and computational issues. Fortunately, there exist interpolation functions with local support known as compactly supported radial basis functions (CSRBFs). These functions produce a sparse and well-conditioned interpolation matrix, especially for large-scale problems. Therefore, this paper aims to apply DRM based on multiquadrics (MQ) RBFs and CSRBFs for evaluation of the Poisson equation, especially for large-scale problems. Furthermore, the convergence analysis of DRM with MQ and CSRBFs is performed, along with error estimate and stability analysis. Several experiments are performed to ensure the well-conditioned, efficient, and accurate behavior of the CSRBFs compared to the MQ-RBFs, especially for large-scale interpolation points.

Conventional wisdom dictates that learning rate should be in the stable regime so that gradient-based algorithms don't blow up. This letter introduces a simple scenario where an unstably large learning rate scheme leads to a super fast convergence, with the convergence rate depending only logarithmically on the condition number of the problem. Our scheme uses a Cyclical Learning Rate (CLR) where we periodically take one large unstable step and several small stable steps to compensate for the instability. These findings also help explain the empirical observations of [Smith and Topin, 2019] where they show that CLR with a large maximum learning rate can dramatically accelerate learning and lead to so-called "super-convergence". We prove that our scheme excels in the problems where Hessian exhibits a bimodal spectrum and the eigenvalues can be grouped into two clusters (small and large). The unstably large step is the key to enabling fast convergence over the small eigen-spectrum.

In this paper, we extend matrix scaled total least squares (MSTLS) problem with a single right-hand side to the case of multiple right-hand sides. Firstly, under some mild conditions, this paper gives an explicit expression of the minimum norm solution of MSTLS problem with multiple right-hand sides. Then, we present the Kronecker-product-based formulae for the normwise, mixed and componentwise condition numbers of the MSTLS problem. For easy estimation, we also exhibit Kronecker-product-free upper bounds for these condition numbers. All these results can reduce to those of the total least squares (TLS) problem which were given by Zheng et al. Finally, two numerical experiments are performed to illustrate our results.

A situation in which an image is combined with multiple images to form interferometric pairs is often observed in small baseline subset-interferometric synthetic aperture radar (SBAS-InSAR) deformation inversion, and this situation leads to a near linear correlation between the column vectors of the model design matrix. The Liu-type estimator introduces the parameters $k$ and $d$ into the normal equation to reduce the condition number of the design matrix and to improve the fitting properties. As the parameter $k$ is mainly used to reduce ill-posed problems of the design matrix, the value of $k$ is not limited. However, the value of $k$ , as determined by existing methods, is usually too large or too small. Since the calculation of the mean square error involves true values, the parameter $d$ is often affected by errors in the estimation results, which leads to the decreased accuracy of Liu-type estimation results. To determine the optimal value of $d$ , an iterative Liu-type estimator is proposed to eliminate errors. Then, the $L$ -curve optimization method and iterative Liu-type estimator are combined to achieve the optimal $k$ . The reliability and accuracy of the methods are analyzed through SBAS-InSAR deformation experiments. The experimental results show that after using the $L$ -curve method and an iterative operation to optimize $k$ and $d$ , the accuracy of the Liu-type estimator based on parameter optimization is clearly improved compared with that of the ridge estimator and the Liu-type estimator.

A widely used form of test matrix is the randsvd matrix constructed as the product $A = U \Sigma V^*$, where $U$ and $V$ are random orthogonal or unitary matrices from the Haar distribution and $\S...

A preconditioner for the mass matrix for high order finite element discretization on tetrahedra is presented and shown to give a condition number that is independent of both the mesh size and the p...

In this paper, we develop a family of high order cut discontinuous Galerkin (DG) methods for hyperbolic conservation laws in one space dimension. The ghost penalty stabilization is used to stabilize the scheme for small cut elements. The analysis shows that our proposed methods have similar stability and accuracy properties as the standard DG methods on a regular mesh. We also prove that the cut DG method with piecewise constants in space is total variation diminishing (TVD). We use the strong stability preserving Runge-Kutta method for time discretization and the time step is independent of the size of cut element. Numerical examples demonstrate that the cut DG methods are high order accurate for smooth problems and perform well for discontinuous problems., Comment: 29 pages, 10 figures

One of the main advantages of second-order methods in a centralized setting is that they are insensitive to the condition number of the objective function's Hessian. For applications such as regression analysis, this means that less pre-processing of the data is required for the algorithm to work well, as the ill-conditioning caused by highly correlated variables will not be as problematic. Similar condition number independence has not yet been established for distributed methods. In this paper, we analyze the performance of a simple distributed second-order algorithm on quadratic problems and show that its convergence depends only logarithmically on the condition number. Our empirical results indicate that the use of second-order information can yield large efficiency improvements over first-order methods, both in terms of iterations and communications, when the condition number is of the same order of magnitude as the problem dimension.

In this paper, a kind of finite-difference lattice Boltzmann method with the second-order accuracy of time and space (T2S2-FDLBM) is proposed. In this method, a two-stage time-accurate discretization approach is applied to construct time marching scheme, and the spatial gradient operator is discretized by a mixed difference scheme to maintain a second-order accuracy in space. It is shown that the previous finite-difference lattice Boltzmann method (FDLBM) (Guo and Zhao, 2003) is a special case of the T2S2-FDLBM. Through the von Neumann analysis, the stability of the method is analyzed and two specific T2S2-FDLBMs are discussed. The two T2S2-FDLBMs are applied to simulate some incompressible flows with the non-uniform grids. Compared with other high order FDLBMs, this two T2S2-FDLBMs keep the simplicity of standard lattice Boltzmann method. Compared with the previous FDLBM and lattice Boltzmann method, the two T2S2-FDLBMs are more accurate and more stable. The value of the Courant–Friedrichs–Lewy condition number in our method can be up to 0.9, which also significantly improves the computational efficiency.

In this article, the condition number of the stiffness matrix κ ( K ) is compared for three high order finite element methods (FEMs), i.e., the p-version of the FEM, the spectral element method (SEM), and the NURBS-based isogeometric analysis (IGA). Note that only problems in linear elasticity are considered in the analysis. It is well-known that the condition number is one factor strongly influencing the number of significant digits for direct solvers or the required iteration count for iterative solution schemes. Therefore, it is important to investigate the effect of the choice of the shape functions and the element distortion on κ ( K ) . Based on numerous one- and two-, and three-dimensional examples, these influences are comprehensively studied, and the numerical results are compared with condition number estimates extracted from the literature. Overall, a good agreement is observed for p-FEM, SEM and two-dimensional IGA, while discrepancies are noted for three-dimensional isogeometric elements. These are important findings as theoretical results may be only available for very restricted scenarios, where one-element geometries, constant Jacobi matrices of the element maps, etc. are considered.