Search

Following the breakthrough work of Tardos (Oper Res 34:250–256, 1986) in the bit-complexity model, Vavasis and Ye (Math Program 74(1):79–120, 1996) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) $$\max \, c^\top x,\, Ax = b,\, x \ge 0,\, A \in \mathbb {R}^{m \times n}$$ max c ⊤ x , A x = b , x ≥ 0 , A ∈ R m × n , Vavasis and Ye developed a primal-dual interior point method using a ‘layered least squares’ (LLS) step, and showed that $$O(n^{3.5} \log (\bar{\chi }_A+n))$$ O ( n 3.5 log ( χ ¯ A + n ) ) iterations suffice to solve (LP) exactly, where $$\bar{\chi }_A$$ χ ¯ A is a condition measure controlling the size of solutions to linear systems related to A. Monteiro and Tsuchiya (SIAM J Optim 13(4):1054–1079, 2003), noting that the central path is invariant under rescalings of the columns of A and c, asked whether there exists an LP algorithm depending instead on the measure $$\bar{\chi }^*_A$$ χ ¯ A ∗ , defined as the minimum $$\bar{\chi }_{AD}$$ χ ¯ AD value achievable by a column rescaling AD of A, and gave strong evidence that this should be the case. We resolve this open question affirmatively. Our first main contribution is an $$O(m^2 n^2 + n^3)$$ O ( m 2 n 2 + n 3 ) time algorithm which works on the linear matroid of A to compute a nearly optimal diagonal rescaling D satisfying $$\bar{\chi }_{AD} \le n(\bar{\chi }_A^*)^3$$ χ ¯ AD ≤ n ( χ ¯ A ∗ ) 3 . This algorithm also allows us to approximate the value of $$\bar{\chi }_A$$ χ ¯ A up to a factor $$n (\bar{\chi }_A^*)^2$$ n ( χ ¯ A ∗ ) 2 . This result is in surprising contrast to that of Tunçel (Math Program 86(1):219–223, 1999), who showed NP-hardness for approximating $$\bar{\chi }_A$$ χ ¯ A to within $$2^{\textrm{poly}(\textrm{rank}(A))}$$ 2 poly ( rank ( A ) ) . The key insight for our algorithm is to work with ratios $$g_i/g_j$$ g i / g j of circuits of A—i.e., minimal linear dependencies $$Ag=0$$ A g = 0 —which allow us to approximate the value of $$\bar{\chi }_A^*$$ χ ¯ A ∗ by a maximum geometric mean cycle computation in what we call the ‘circuit ratio digraph’ of A. While this resolves Monteiro and Tsuchiya’s question by appropriate preprocessing, it falls short of providing either a truly scaling invariant algorithm or an improvement upon the base LLS analysis. In this vein, as our second main contribution we develop a scaling invariant LLS algorithm, which uses and dynamically maintains improving estimates of the circuit ratio digraph, together with a refined potential function based analysis for LLS algorithms in general. With this analysis, we derive an improved $$O(n^{2.5} \log (n)\log (\bar{\chi }^*_A+n))$$ O ( n 2.5 log ( n ) log ( χ ¯ A ∗ + n ) ) iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor $$n/\log n$$ n / log n improvement on the iteration complexity bound of the original Vavasis–Ye algorithm.

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 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.

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.

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 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 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.

We consider three models of sparse random graphs: undirected and directed Erdős–Renyi graphs and random bipartite graph with two equal parts. For such graphs, we show that if the edge connectivity probability p satisfies $$np\ge \log n+k(n)$$ with $$k(n)\rightarrow \infty $$ as $$n\rightarrow \infty $$ , then the adjacency matrix is invertible with probability approaching one (n is the number of vertices in the two former cases and the same for each part in the latter case). For $$np\le \log n-k(n)$$ these matrices are invertible with probability approaching zero, as $$n\rightarrow \infty $$ . In the intermediate region, when $$np=\log n+k(n)$$ , for a bounded sequence $$k(n)\in \mathbb {R}$$ , the event $$\Omega _0$$ that the adjacency matrix has a zero row or a column and its complement both have a non-vanishing probability. For such choices of p our results show that conditioned on the event $$\Omega _0^c$$ the matrices are again invertible with probability tending to one. This shows that the primary reason for the non-invertibility of such matrices is the existence of a zero row or a column. We further derive a bound on the (modified) condition number of these matrices on $$\Omega _0^c$$ , with a large probability, establishing von Neumann’s prediction about the condition number up to a factor of $$n^{o(1)}$$ .

To solve the linear systems of equations Ax = b on a quantum computer, Shao and Xiang proposed a quantum version of row and column methods by establishing unitary operators in each iteration step based on the block-encoding technique in Shao and Xiang (Phys. Rev. A 101, 022322, 2020]. In this paper, we generalize this strategy for solving the linear systems of equations Ax = b by an extended randomized row and column method on a quantum computer, where both the rows and columns of coefficient matrix are used via the block-encoding technique. If the quantum states are effectively prepared, compared with its traditional counterpart, our quantum iterative algorithm achieves an exponential speedup in the problem dimension n. The complexity of the quantum extended row and column method is $O({{\kappa _{s}^{2}}(A)}(\log n) \log {1}/{\epsilon })$ , where κs(A) is the scaled condition number of A, and 𝜖 is the error.

A novel hybrid perfusion manipulator (HPM) with five degrees of freedom (DOFs) is introduced by combining the 5PUS-PRPU (P, R, U, and S represent prismatic, revolute, universal, and spherical joint, respectively) parallel mechanism with the 5PRR reconfigurable base to enhance the perfusion efficiency of the large-scale spherical honeycomb thermal protection layer. This study mainly presents the dimensional synthesis of the proposed HPM. First, the inverse kinematics, including the analytic expression of the rotation angles of the U joint in the PUS limb, is obtained, and mobility analysis is conducted based on screw theory. The Jacobian matrix of 5PUS-PRPU is also determined with screw theory and used for the establishment of the objective function. Second, a global and comprehensive objective function (GCOF) is proposed to represent the Jacobian matrix’s condition number. With the genetic algorithm, dimensional synthesis is conducted by minimizing GCOF subject to the given variable constraints. The values of the designed variables corresponding to different configurations of the reconfigurable base are then obtained. Lastly, the optimal structure parameters of the proposed 5-DOF HPM are determined. Results show that the HPM with the optimized parameters has an enlarged orientation workspace, and the maximum angle of the reconfigurable base is decreased, which is conducive to improving the overall stiffness of HPM.

This paper presents a quantum algorithm to decide whether a Boolean equation system F has a solution and to compute one if F does have solutions with any given success probability. The runtime complexity of the algorithm is polynomial in the size of F and the condition number of certain Macaulay matrix associated with F. As a consequence, the authors give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are polynomial in the size of F. The authors apply the proposed quantum algorithm to the cryptanalysis of several important cryptosystems: The stream cipher Trivum, the block cipher AES, the hash function SHA-3/Keccak, the multivariate public key cryptosystems, and show that they are secure under quantum algebraic attack only if the corresponding condition numbers are large. This leads to a new criterion for designing such cryptosystems which are safe against the attack of quantum computers: The corresponding condition number.

The linear regression model is widely applied to measure the relationship between a dependent variable and a set of independent variables. When the independent variables are related to each other, it is said that the model presents collinearity. If the relationship is between the intercept and at least one of the independent variables, the collinearity is nonessential, while if the relationship is between the independent variables (excluding the intercept), the collinearity is essential. The Stewart index allows the detection of both types of near multicollinearity. However, to the best of our knowledge, there are no established thresholds for this measure from which to consider that the multicollinearity is worrying. This is the main goal of this paper, which presents a Monte Carlo simulation to relate this measure to the condition number. An additional goal of this paper is to extend the Stewart index for its application after the estimation by ridge regression that is widely applied to estimate model with multicollinearity as an alternative to ordinary least squares (OLS). This extension could be also applied to determine the appropriate value for the ridge factor.

The excitation force of under-chassis active equipment of railway vehicles has a significant impact on the flexible vibration of the car body. Mastering the excitation force of equipment can control the vehicle body vibration more comprehensively. To identify the excitation force of under-chassis equipment of railway vehicles, four frequency-based force identification methods such as least square method and Tikhonov regularization methods based on L-Curve, ordinary cross-validation, and generalized cross-validation respectively, are studied. Laboratory test shows the effectiveness of the above identification methods. A plate model is used to analyze the influence of the measuring positions and measuring noise on the identification accuracy of different types of excitation forces. It is found that it is a suitable method to determine the optimal combination of measuring points according to the optimal condition number criterion. Based on the finite element model of the car body with under-chassis equipment, the excitation force of the under-chassis equipment is identified, and the validity of the optimal condition number criterion is verified. In addition, the results show that when the frequency response function and the responses of measuring points are disturbed by noise, the above methods show different robustness to the models with different degrees of complexity. The equipment structure of railway vehicles is complicated, which is easy to be disturbed by noise in the actual test, and the signal-to-noise ratio is small. Therefore, it may be appropriate to choose Tikhonov regularization based on the L-Curve.

In this paper we alleviate limitations of the conventional embedded reinforcement formulation for applications with dense fiber contents. We demonstrate that by condensing the fiber degrees of freedom during the assembly stage, the condition number of the resultant stiffness matrix is effectively reduced and the use of iterative solvers is facilitated even without preconditioning. Numerical benchmarks consisting of very large numbers of high aspect ratio discrete fibers are performed, and major advantages are reported in terms of the computational efficiency of the solution method. We apply the solution method to a set of examples in the modeling of the fiber reinforced composites, specifically the estimation of the homogenized mechanical properties of the discontinuous fiber composites and modeling of the compression molding process. In the latter case, a specimen containing more than 2 million discrete fibers is analyzed.

This paper offers a review of numerical methods for computation of the eigenvalues of Hermitian matrices and the singular values of general and some classes of structured matrices. The focus is on the main principles behind the methods that guarantee high accuracy even in the cases that are ill-conditioned for the conventional methods. First, it is shown that a particular structure of the errors in a finite precision implementation of an algorithm allows for a much better measure of sensitivity and that computation with high accuracy is possible despite a large classical condition number. Such structured errors incurred by finite precision computation are in some algorithms e.g. entry-wise or column-wise small, which is much better than the usually considered errors that are in general small only when measured in the Frobenius matrix norm. Specially tailored perturbation theory for such structured perturbations of Hermitian matrices guarantees much better bounds for the relative errors in the computed eigenvalues. % Secondly, we review an unconventional approach to accurate computation of the singular values and eigenvalues of some notoriously ill-conditioned structured matrices, such as e.g. Cauchy, Vandermonde and Hankel matrices. The distinctive feature of accurate algorithms is using the intrinsic parameters that define such matrices to obtain a non-orthogonal factorization, such as the \textsf{LDU} factorization, and then computing the singular values of the product of thus computed factors. The state of the art software is discussed as well.

In this paper, we first consider the time-harmonic Maxwell equations with Dirichlet boundary conditions in three-dimensional anisotropic media, where the coefficients of the equations are general symmetric positive definite matrices. By using scaling transformations and coordinate transformations, we build the desired stability estimates between the original electric field and the transformed nonphysical field on the condition number of the anisotropic coefficient matrix. More importantly, we prove that the resulting approximate solutions generated by plane wave least squares (PWLS) methods have the nearly optimal L2 error estimates with respect to the condition number of the coefficient matrix. Finally, numerical results verify the validity of the theoretical results, and the comparisons between the proposed PWLS method and the existing PWDG method are also provided.

The aim of this work is to study the solution of the smoothed particle hydrodynamics (SPH) discrete formulation of the hydrostatic problem with a free surface. This problem, in which no time dependency is considered, takes the form of a system of linear equations. In particular, the problem in one dimension is addressed. The focus is set on the convergence when both the particle spacing and the smoothing length tend to zero by keeping constant their ratio. Values of this ratio of the order of one, corresponding to a limited number of neighbors, are of practical interest. First, the problem in which each particle has one single neighbor at each side is studied. The explicit expressions of the numerical solution and the quadratic error are provided in this case. The expression of the quadratic error demonstrates that the SPH solution does not converge to the exact one in general under the specified conditions. In this case, the error converges to a residue, which is in general large compared to the norm of the exact solution. The cases with two and three neighbors are also studied. An analytical study in the case of two neighbors is performed, showing how the kernel influences the accuracy of the solution through modifying the condition number of the referred system of linear equations. In addition to that, a numerical investigation is carried out using several Wendland kernel formulas. When two and three neighbors are involved it is found that the error tends in most cases to a small limiting value, different from zero, while divergent solutions are also found in the case of two neighbors with the Wendland Kernel C2. Other cases with more neighbors are also considered. In general, the Wendland Kernel C2. turns out to be the worst choice, as the solution is divergent for certain values of the ratio between the particle spacing and the smoothing length, associated with an ill-conditioned matrix.

The radiative–conductive transfer equation in the $$S_N$$ approximation for spherical geometry is solved using a modified decomposition method. The focus of this work is to show how to distribute the source terms in the recursive equation system in order to guarantee arithmetic stability and thus numerical convergence of the obtained solution, guided by a condition number criterion. Some examples are compared with results from literature and parameter combinations are analyzed, for which the condition number analysis indicates convergence of the solutions obtained by the recursive scheme.

We investigate the solution of linear systems of equations that arise when singularly perturbed reaction–diffusion partial differential equations are solved using a standard finite difference method on layer adapted grids. It is known that there are difficulties in solving such systems by direct methods when the perturbation parameter, $$\varepsilon $$ , is small (MacLachlan and Madden in SIAM J Sci Comput 35(5):A2225–A2254, 2013). Therefore, iterative methods are natural choices. However, we show that, in two dimensions, the condition number of the coefficient matrix grows unboundedly when $$\varepsilon $$ tends to zero, and so unpreconditioned iterative schemes, such as the conjugate gradient algorithm, perform poorly with respect to $$\varepsilon $$ . We provide a careful analysis of diagonal and incomplete Cholesky preconditioning methods, and show that the condition number of the preconditioned linear system is independent of the perturbation parameter. We demonstrate numerically the surprising fact that these schemes are more efficient when $$\varepsilon $$ is small, than when $$\varepsilon $$ is $$\mathcal {O}(1)$$ . Furthermore, our analysis shows that when the singularly perturbed problem features no corner layers, an incomplete Cholesky preconditioner performs extremely well when $$\varepsilon \ll 1$$ . We provide numerical evidence that our findings extend to three-dimensional problems.

To guarantee heredity of positive definiteness under the popular Wolfe line search conditions, a modification is made on the symmetric rank–one updating formula, a simple quasi–Newton approximation for (inverse) Hessian of the objective function of an unconstrained optimization problem. Then, the scaling approach is employed on a memoryless version of the proposed formula, leading to an iterative method which is appropriate for solving large–scale problems. Based on an eigenvalue analysis, it is shown that the self–scaling parameter proposed by Oren and Spedicato is an optimal parameter for the proposed updating formula in the sense of minimizing the condition number. Also, a sufficient descent property is established for the method, together with a global convergence analysis for uniformly convex objective functions. Numerical experiments demonstrate computational efficiency of the proposed method with the self–scaling parameter proposed by Oren and Spedicato.

Global navigation satellite system (GNSS) positioning depends on the correct integer ambiguity resolution (AR). If the double difference equation for solving the float solution remains ill-conditioned, often happening due to the environment complexity and the equipment mobility, the correct AR is difficult to achieve. Concerning the ill-conditioned problem, methods of modifying the equation coefficient matrix are widely applied, whose effects are heavily dependent on modifying parameters. Besides, the direct-inversion of the ill-conditioned coefficient matrix can lead to a reduction in the accuracy and stability of the float solution. To solve the problem of ill-conditioned matrix inversion and further improve the accuracy, the present study for the first time proves the positive definite symmetry of the coefficient matrix in AR model and employs precise integration method to the indirect inverse of coefficient matrix. AR model for the GNSS positioning and the general resolving strategies introduction are briefly introduced. An indirect-inversion algorithm via precise integration for ill-conditioned coefficient matrix is proposed. According to the simulations and comparisons, the proposed strategy has higher precision and stability on float solution, and less dependence on modifying parameters.

Aimed to improve the stiffness identification precision of 7-degree-of-freedom (Dof) collaborative robots (Cobots), an optimal configuration selection method for elastostatic calibration of robots is researched by the influencing factor separation method. Different from previous studies, this method can deal with the influence of redundant Dof on measurement configuration selection of redundant robotic manipulators. The independent influence of each joint on the inverse condition number which is selected as the evaluation criterion is analyzed through the orthogonal design experiment and the analysis of variance, and the optimal measuring configurations of robots for stiffness identification can be selected from joint space. Based on a 7-Dof Cobot SHIR5-III, static compliance simulations are performed to identify joint stiffness of the robot. Compared to identification results by using the configurations having large, medium and small inverse condition number, the effectiveness of this optimal configuration selection method is verified and the identification accuracy can be essentially improved with configurations having a large inverse condition number.

The condition number of a differentiable convex function, namely the ratio of its smoothness to strong convexity constants, is closely tied to fundamental properties of the function. In particular, the condition number of a quadratic convex function is the square of the aspect ratio of a canonical ellipsoid associated to the function. Furthermore, the condition number of a function bounds the linear rate of convergence of the gradient descent algorithm for unconstrained convex minimization. We propose a condition number of a differentiable convex function relative to a reference convex set and distance function pair. This relative condition number is defined as the ratio of relative smoothness to relative strong convexity constants. We show that the relative condition number extends the main properties of the traditional condition number both in terms of its geometric insight and in terms of its role in characterizing the linear convergence of first-order methods for constrained convex minimization. When the reference set X is a convex cone or a polyhedron and the function f is of the form $$f = g\circ A$$ , we provide characterizations of and bounds on the condition number of f relative to X in terms of the usual condition number of g and a suitable condition number of the pair (A, X).

The nonlinear matrix equation $$X^p=R+M^T(X^{-1}+B)^{-1}M$$ , where p is a positive integer, M is an arbitrary $$n\times n$$ real matrix, R and B are symmetric positive semidefinite matrices, is considered. When $$p=1$$ , this matrix equation is the well-known discrete-time algebraic Riccati equation (DARE), we study the convergence rate of an iterative method which was proposed in Meng and Kim (J Comput Appl Math 322:139–147, 2017). For the generalized case $$p\ge 1$$ , a structured condition number based on the classic definition of condition number is defined and its explicit expression is obtained. Finally, we give some numerical examples to show the sharpness of the structured condition number.

In this paper, a new iterative refinement for ill-conditioned linear systems is derived based on discrete gradient methods for gradient systems. It is proved that the new method is convergent for any initial values irrespective of the choice of the stepsize h. Some properties of the new iterative refinement are presented. It is shown that the condition number of the coefficient matrix in the linear system to be solved in every step can be improved significantly compared with Wilkinson’s iterative refinement. The numerical experiments illustrate that the new method is more effective and efficient than Wilkinson’s iterative refinement when dealing with ill-conditioned linear systems.

We consider ill-conditioned matrices of systems of linear algebraic equations with random error of vector right-hand side. We study the condition number ν of the matrix of the system. We show that, under certain natural assumptions, the number ν can be considerably diminished. Bibliography: 3 titles. Illustrations: 3 figures.

In general, interior point methods are successful in solving large-scale linear programming problems. Their effectiveness is determined by how fast they calculate each solution of a linear system. When solving large-scale linear systems, iterative methods are useful options since they require slightly more computational memory in each iteration and preserve the sparsity pattern of the matrix system. In this context, a common choice is the conjugate gradient method using a preconditioning strategy. Choosing a single preconditioner that fits well during all iterations of the optimization method is not an easy task, because the distribution of the eigenvalues of the system matrix may vary significantly from the first to the last iterations. In order to simplify this task, one can use different preconditioners in different iterations, in a hybrid preconditioner strategy. In the case of symmetric positive definite systems, the Controlled Cholesky Factorization achieves excellent performance for the first interior point iterations, whereas the Splitting preconditioner is very useful in the last iterations. However, since we apply a hybrid approach combining both preconditioners, it is necessary to decide when using each preconditioner. This paper addresses the critical issue of choosing between the two preconditioners of the hybrid strategy by using the condition number of the matrix system. The Ritz values obtained from the conjugate gradient method provide an approximation to the eigenvalues, which offers an estimate of the condition number. The main contribution of this research is a new heuristic to switching the preconditioners based on the estimated condition number. Numerical results for large-scale problems show that our choice to change the preconditioners adds both speed and robustness to a hybrid approach that combines the Controlled Cholesky Factorization and the Splitting preconditioner.

HHL algorithm is a quantum algorithm for solving linear equation system. It can achieve an exponential improvement over the best classical algorithm. In this paper, we analyze the quantum security of Grain-128/Grain-128a stream cipher by using the HHL algorithm. Our algorithm is based on Chen and Gao’s research on solving nonlinear equation system in Chen et al. (Quantum algorithm for optimization and polynomial system solving over finite field and application to cryptanalysis, 2018. arXiv:1802.03856 ) and Chen et al. (Quantum algorithms for Boolean equation solving and quantum algebraic attack on cryptosystems, 2017. arXiv:1712.06239 ). Firstly, we build a nonlinear Boolean equation system by choosing any keystream. Then, the nonlinear equation system is transformed into a special linear equation system that can be solved with the HHL algorithm. Finally, we solve the system by the HHL quantum algorithm. Our attack requires $$ N > {2^8} $$ -bit keystream, and the complexity is $$O(2^{21} N^{3.5} \kappa ^2 e^\epsilon /\epsilon ^{0.5})$$ for Grain-128, and $$O(2^{21.5} N^{3.5} \kappa ^2 e^\epsilon /\epsilon ^{0.5})$$ for Grain-128a where $$\kappa $$ is the condition number of the matrix of the corresponding linear systems and $$\epsilon $$ is a given error bound. Then we give a toy example of Grain family to estimate $$\kappa $$ and briefly analyze the security of Grain-128/Grain-128a against HHL algorithm.

The aim of this paper is to derive a new family of multi-block boundary value methods based on multi-block generalized Adams methods for numerical solution of stiff problems. Generally, boundary value methods easily circumvents the Dahlquist stability barrier in linear multistep formulas. This leads to a new stability framework for multi-block boundary value methods (MB $$_2$$ VMs) with the aid of the Wiener–Hopf factorization of a matrix polynomial, which generalizes the stability of initial multi-block methods in Chu and Hamilton (SIAM J Sci Stat Comput 8:342–535, 1987). The condition number of the arising Toeplitz matrix for the MB $$_2$$ VMs are very small, and in general are bounded. The MB $$_2$$ VMs are new classes of very large scale integration methods for the numerical solution of differential equations which output multi-block of solutions on application. Numerical experiments are presented and compared with some existing ones.

Analytic continuation is ill-posed, but becomes merely ill-conditioned (although with an infinite condition number) if it is known that the function in question is bounded in a given region of the complex plane. In an annulus, the Hadamard three-circles theorem implies that the ill-conditioning is not too severe, and we show how this explains the effectiveness of Chebfun and related numerical methods in evaluating analytic functions off the interval of definition. By contrast, we show that analytic continuation is far more ill-conditioned in a strip or a channel, with exponential loss of digits of accuracy at the rate $$\exp (-\pi x/2)$$ exp ( - π x / 2 ) as one moves along. The classical Weierstrass chain-of-disks method loses digits at the faster rate $$\exp (-ex)$$ exp ( - e x ) .

In this paper, a second order finite difference scheme is investigated for time-dependent one-side space fractional diffusion equations with variable coefficients. The existing schemes for the equation with variable coefficients have temporal convergence rate no better than second order and spatial convergence rate no better than first order, theoretically. In the presented scheme, the Crank-Nicolson temporal discretization and a second-order weighted-and-shifted Gr\"unwald-Letnikov spatial discretization are employed. Theoretically, the unconditional stability and the second-order convergence in time and space of the proposed scheme are established under some conditions on the diffusion coefficients. Moreover, a Toeplitz preconditioner is proposed for linear systems arising from the proposed scheme. The condition number of the preconditioned matrix is proven to be bounded by a constant independent of the discretization step-sizes so that the Krylov subspace solver for the preconditioned linear systems converges linearly. Numerical results are reported to show the convergence rate and the efficiency of the proposed scheme.

Nuclear magnetic resonance (NMR) log is a powerful tool to obtain porosity and oil saturation in reservoir evaluation. NMR echo inversion, however, may give poor information in the two parameters if the ratio of signal-to-noise is not so good. Combining NMR log and some conventional logs, such as GR log, sonic log, and density log, a novel inversion algorithm is developed in this research. First, normalize the logging response, then, insert both the logging response equations and the definition equations of volume model into the NMR echo equations. By conducting the data inversion for both NMR echo and conventional logging data, the porosity and oil saturation can be calculated. The condition number of the inversion matrix is decreased, so, the inversion parameters own better stability and the random weak noise is stifled. Furthermore, the T2 spectral distribution derived from the new inversion seems to be sensitive to the small pores in tight reservoir. Due to the weak noise removal and sensitiveness of small pore, the novel inversion may be utilized in reservoir evaluation in shale oil and gas, such as the identification of “sweet spot”.

Magnetorelaxometry imaging is a highly sensitive technique enabling noninvasive, quantitative detection of magnetic nanoparticles. Electromagnetic coils are sequentially energized, aligning the nanoparticles’ magnetic moments. Relaxation signals are recorded after turning off the coils. The forward model describing this measurement process is reformulated into a severely ill-posed inverse problem that is solved for estimating the particle distribution. Typically, many activation sequences employing different magnetic fields are required to obtain reasonable imaging quality. We seek to improve the imaging quality and accelerate the imaging process using fewer activation sequences by optimizing the applied magnetic fields. Minimizing the Frobenius condition number of the system matrix, we stabilize the inverse problem solution toward model uncertainties and measurement noise. Furthermore, our sensitivity-weighted reconstruction algorithms improve imaging quality in lowly sensitive areas. The optimization approach is employed to real measurement data and yields improved reconstructions with fewer activation sequences compared to non-optimized measurements.

Application of condition number (CN) approach is critical in selecting appropriate combination of probe liquids for evaluating the surface free energy (SFE) of bitumen. The CN approach recommends use of probe liquids with CN 10 without concerning its adverse effects on the SFE of bitumen. Inappropriate choice of probe liquids may result in incorrect SFE values of bitumen, thereby influencing its compatibility with aggregates. Therefore, the present study is strongly motivated to exhibit the application of CN approach for selecting appropriate probe liquids. Further investigating the impact of CN on aggregate-bitumen compatibility, the present research work also aims at validating CN approach. A polymer modified bitumen (i.e., PMB40) and two types of aggregates namely, quartzite, and basalt aggregates were selected in this study. Five probe liquids namely, water, formamide, diiodomethane, ethylene glycol and glycerol were selected, which formed ten different combinations of probe liquid triplets. The CN of probe liquid triplets was calculated based on singular value decomposition (SVD) method. Thereafter, using the SFE of aggregates and bitumen, compatibility of basalt-PMB40 and quartzite-PMB40 was evaluated using compatibility ratio (CR) parameter. Results revealed that except for probe liquids triplets with CN 10. Therefore, the present study addresses the adverse effect of inappropriate selection of probe liquids on aggregate-bitumen compatibility and also validates the CN approach.

The scalar wave equation is solved using higher order immersed finite elements. We demonstrate that higher order convergence can be obtained. Small cuts with the background mesh are stabilized by adding penalty terms to the weak formulation. This ensures that the condition numbers of the mass and stiffness matrix are independent of how the boundary cuts the mesh. The penalties consist of jumps in higher order derivatives integrated over the interior faces of the elements cut by the boundary. The dependence on the polynomial degree of the condition number of the stabilized mass matrix is estimated. We conclude that the condition number grows extremely fast when increasing the polynomial degree of the finite element space. The time step restriction of the resulting system is investigated numerically and is concluded not to be worse than for a standard (non-immersed) finite element method.

The boundary knot method (BKM) is a boundary-type meshfree method. Only non-singular general solutions are used during the whole solution procedures. The effective condition number (ECN), which depends on the right-hand side vector of a linear system, is considered as an alternative criterion to the traditional condition number. In this paper, the effective condition number is used to help determine the position and distribution of the collocation points as well as the quasi-optimal collocation point numbers. During the solution process, we propose an NMN-search algorithm. Numerical examples show that the ECN is reliable to measure the feasibility of the BKM.

The eigenvector-dependent nonlinear eigenvalue problem (NEPv) $A(P)V=V\Lambda$, where the columns of $V\in\mathbb{C}^{n\times k}$ are orthonormal, $P=VV^{\mathrm{H}}$, $A(P)$ is Hermitian, and $\Lambda=V^{\mathrm{H}}A(P)V$, arises in many important applications, such as the discretized Kohn-Sham equation in electronic structure calculations and the trace ratio problem in linear discriminant analysis. In this paper, we perform a perturbation analysis for the NEPv, which gives upper bounds for the distance between the solution to the original NEPv and the solution to the perturbed NEPv. A condition number for the NEPv is introduced, which reveals the factors that affect the sensitivity of the solution. Furthermore, two computable error bounds are given for the NEPv, which can be used to measure the quality of an approximate solution. The theoretical results are validated by numerical experiments for the Kohn-Sham equation and the trace ratio optimization., Comment: 25 pages, 12 figures

The paper describes the configuring and analysis of a class of generalized reconfigurable 2-axis parallel kinematic machine (R2PKM). A generalized model which is used for solving inverse and direct kinematic problem is presented. Generalized equations that present the solutions of kinematic problems are derived and they are valid for any configuration of R2PKM. Characteristic configurations of the mechanism are given as an example of the concept realization. For selected configurations, workspaces are defined and possible singular positions of the mechanism are analyzed. Optimization of the mechanism legs length was performed using the condition number. Determination of optimal legs length has been shown for several different configurations of the parallel mechanism. Control and programming system is configured and experimental prototype of R2PKM is realized. Verification of the configured machine, configured control and programming system was performed on the virtual machine and also on the prototype of the machine by drawing several different contours.

Optimization over low rank matrices has broad applications in machine learning. For large-scale problems, an attractive heuristic is to factorize the low rank matrix to a product of two much smaller matrices. In this paper, we study the nonconvex problem $$\min _{\mathbf {U}\in \mathbb {R}^{n\times r}} g(\mathbf {U})=f(\mathbf {U}\mathbf {U}^T)$$ under the assumptions that $$f(\mathbf {X})$$ is restricted $$\mu $$ -strongly convex and L-smooth on the set $$\{\mathbf {X}:\mathbf {X}\succeq 0,\text{ rank }(\mathbf {X})\le r\}$$ . We propose an accelerated gradient method with alternating constraint that operates directly on the $$\mathbf {U}$$ factors and show that the method has local linear convergence rate with the optimal dependence on the condition number of $$\sqrt{L/\mu }$$ . Globally, our method converges to the critical point with zero gradient from any initializer. Our method also applies to the problem with the asymmetric factorization of $$\mathbf {X}={\widetilde{\mathbf {U}}}{\widetilde{\mathbf {V}}}^T$$ and the same convergence result can be obtained. Extensive experimental results verify the advantage of our method.

When model-based controllers are used for carrying out precise tasks, the estimation of model parameters is key for a better trajectory tracking performance. We consider the scenario of a free-flying space robot with limited actuation that has grasped an object of unknown properties. The inertial parameters - mass, centre of mass and the inertia tensor - of the robot-object system are to be determined. In our previous works, we used a parameter estimation algorithm where truncated Fourier series were used to represent both the reference excitation trajectory and the executed one. That algorithm is the focus of this paper, along with a study of the factors that could contribute to a loss of accuracy in the obtained estimates. Simulation results with the Space CoBot free-flyer robot are used to find the causes of the latter: first, a modified version of the minimum condition number criterion is used to generate feasible excitatory trajectories. The results are compared with those given by the maximum information criterion to check for better excitation. Next, an appropriate number of harmonics has to be found for the Fourier series, which will be used to fit the measured data. This is done autonomously, based on the least squares residual. Finally, the relation between input saturation while executing the excitation trajectory and the errors in the resulting parameter estimates is studied.

This note surveys recent strategies to estimate the condition number $$CN(T)=\Vert T\Vert \cdot \Vert T^{-1}\Vert $$ of complex $$n\times n$$ matrices T with given spectrum. More precisely, we present a proof of the fact that if T acts on the Hilbert space $$\mathbb {C}^{n}$$ , then the supremum of CN(T) over all contractions T with smallest eigenvalues of modulus $$r>0$$ , is equal to $$1/r^{n}$$ , and is achieved by an analytic Toeplitz matrix. The same question is treated for n-dimensional Banach spaces. These strategies provide with explicit and constructive solutions to the so-called Halmos and Schaffer’s problems, and are also shown to be effective in a closely related situation, namely considering Kreiss matrices instead of contractions.

The adaptive simpler block GMRES method was investigated by Zhong et al. (J Comput Appl Math 282:139–156, 2015) where the condition number of the adaptively chosen basis for the Krylov subspace was evaluated. In this paper, the new upper bound for the condition number is investigated. Numerical tests show that the new upper bound is tighter.

We study the average condition number for polynomial eigenvalues of collections of matrices drawn from some random matrix ensembles. In particular, we prove that polynomial eigenvalue problems defined by matrices with random Gaussian entries are very well conditioned on the average.

In this paper numerical solution of 3D convection–diffusion problems both with high Reynolds (Re) numbers and variable coefficients are investigated via a meshless method based on polynomial basis. It is well known that using polynomial basis directly for solving partial differential equations may be unsafe due to ill-conditioned resultant coefficients matrix that formed after discretization process. Therefore to get rid of highly ill-conditioned coefficient matrix we took advantage of multiple-scale method which is essentially based on the idea of equating norm of each column of resultant coefficients matrix. Through this approach we can reduce the condition number greatly. The proposed method is a truly meshless method since there is no need for meshing or any node connectivity and implementation of the method is simple and straightforward. The performance of the proposed method is measured by four test problems in both regular and irregular computational domains. Numerical results corroborate efficiency of meshless multiple-scale polynomial method for 3D convection–diffusion problems as well show its stability in case of large noise effect.

A novel algorithm to solve the quadratic programming (QP) problem over ellipsoids is proposed. This is achieved by splitting the QP problem into two optimisation sub-problems, (1) quadratic programming over a sphere and (2) orthogonal projection. Next, an augmented-Lagrangian algorithm is developed for this multiple constraint optimisation. Benefitting from the fact that the QP over a single sphere can be solved in a closed form by solving a secular equation, we derive a tighter bound of the minimiser of the secular equation. We also propose to generate a new positive semidefinite matrix with a low condition number from the matrices in the quadratic constraint, which is shown to improve convergence of the proposed augmented-Lagrangian algorithm. Finally, applications of the quadratically constrained QP to bounded linear regression and tensor decomposition paradigms are presented.