Search

This work considers the observability problem in bearings-only tracking (BOT). Although the rank criterion has always been used for observability analysis, the evident drawback that it can only give a qualitative result prevents us from exploiting more information from the observability matrix. In reality, we want to know not only if the system is observable but also the degree of the observability. In order to quantitatively describe the system observability, we propose a series of metrics for BOT. Being derived based on the condition number, the novel metrics can reflect the observability degree as well as evaluate the tracking performance. Besides, the metrics can be extended to be used for sensor trajectory optimization and sensor configuration, which are crucial to enhancing the tracking performance.

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.

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.

Blade Tip-Timing (BTT) has been regarded as a promising way of on-line blade vibration monitoring. But blind multi-band BTT vibration reconstruction is a big challenge under variable speeds and under-sampling. In order to deal with it, a novel Compressed Sensing (CS) method is proposed based on Multi-Coset Angular Sampling (MCAS) in this paper. First, multi-coset sampling scheme of BTT vibration signals is presented. Then the CS model of BTT vibration signals is derived in order domain. A sufficient condition of the number of BTT sensors is derived for perfect reconstruction and optimal placement of BTT sensors is determined by minimizing the condition number. In the end, numerical simulations are done to validate the proposed method and the performances of four reconstruction algorithms are compared, i.e., Orthogonal Matching Pursuit (OMP), Multiple Signal Classification (MUSIC), Basis Pursuit Denoising (BPDN) and Modified Focal Underdetermined System Solver (MFOCUSS). Influences of the sensor placement, the number of BTT sensors and measurement noises on the reconstruction performances are also testified. The results demonstrate that the proposed method is feasible and the overall performance of the BPDN algorithm is the best among the four algorithms. Also the reconstruction performance decreases with the accelerations of rotating speed.

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

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

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.

We propose an adaptive multigrid preconditioning technology for solving linear systems arising from Discontinuous Petrov–Galerkin (DPG) discretizations. Unlike standard multigrid techniques, this preconditioner involves only trace spaces defined on the mesh skeleton, and it is suitable for adaptive hp-meshes. The key point of the construction is the integration of the iterative solver with a fully automatic and reliable mesh refinement process provided by the DPG technology. The efficacy of the solution technique is showcased with numerous examples of linear acoustics and electromagnetic simulations, including simulations in the high-frequency regime, problems which otherwise would be intractable. Finally, we analyze the one-level preconditioner (smoother) for uniform meshes and we demonstrate that theoretical estimates of the condition number of the preconditioned linear system can be derived based on well established theory for self-adjoint positive definite operators.

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.

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.

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.

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.

We propose a two-parameter family of nonsymmetric dense n ⨉ n matrices A(α, β) for which LU factorization without pivoting is numerically stable, and we show how to choose α and β to achieve any value of the ∞-norm condition number. The matrix A(α, β) can be formed from a simple formula in O(n²) flops. The matrix is suitable for use in the HPL-AI Mixed-Precision Benchmark, which requires an extreme scale test matrix (dimension n > 10⁷) that has a controlled condition number and can be safely used in LU factorization without pivoting. It is also of interest as a general-purpose test matrix.

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

We consider a measurement constrained supervised learning problem, that is, (1) full sample of the predictors are given; (2) the response observations are unavailable and expensive to measure. Thus, it is ideal to select a subsample of predictor observations, measure the corresponding responses, and then fit the supervised learning model on the subsample of the predictors and responses. However, model fitting is a trial and error process, and a postulated model for the data could be misspecified. Our empirical studies demonstrate that most of the existing subsampling methods have unsatisfactory performances when the models are misspecified. In this paper, we develop a novel subsampling method, called "LowCon", which outperforms the competing methods when the working linear model is misspecified. Our method uses orthogonal Latin hypercube designs to achieve a robust estimation. We show that the proposed design-based estimator approximately minimizes the so-called "worst-case" bias with respect to many possible misspecification terms. Both the simulated and real-data analyses demonstrate the proposed estimator is more robust than several subsample least squares estimators obtained by state-of-the-art subsampling methods., 37pages, 10 figures

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.

Well-conditioned matrices are often required in science and engineering, such as signal processing and finance. Problem to find the nearest positive definite matrix by explicitly imposing a constraint on the condition number are considered in this paper. A new algorithm based on geometric perspective is proposed for getting the required well-conditioned matrix. Based on these, a condition number-constrained matrix minimization problem is further considered, where the constraints are imposed for avoiding degenerate solutions in which parameter matrices become rank deficient. An inexact version of alternating direction method with truly implementable inexactness criteria is proposed for solving this problem. Numerical experiments, including comparison with some existing methods, are performed to illustrate the efficiency of the proposed algorithms.

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.

Recently, Blanco-Chacón proved the equivalence between the Ring Learning With Errors and Polynomial Learning With Errors problems for some families of cyclotomic number fields by giving some upper bounds for the condition number Cond(Vn ) of the Vandermonde matrix Vn associated to the nth cyclotomic polynomial. We prove some results on the singular values of Vn and, in particular, we determine Cond(Vn ) for n = 2 kpℓ , where k, ℓ ≥ 0 are integers and p is an odd prime 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.

In this paper we give an overview of the Method of Fundamental Solutions (MFS) as a heuristic numerical method. It is truly meshless. Its concept and numerical implementation are simple. It has the flexibility of using various forms of fundamental solutions, singular, hypersingular, or nonsingular, and mixing with general solutions and particular solutions, for different purposes. The collocation matrix, however, is not guaranteed to be invertible. There are other issues. For example, in using the logarithmic fundamental solution, a degenerate scale can exist, causing the nonuniqueness of solution. For metaharmonic operators, such as the Helmholtz equation, the zeros of the fundamental solutions can create spurious resonance frequencies. These and other issues are discussed, and remedies are offered. The traditional error analysis for the MFS shows that when the boundary condition is prescribed by a harmonic function, the convergence is exponential either by increasing the number of terms in the approximation, or by increasing the radius of the fictitious boundary. In practical problems, however, a harmonic boundary condition hardly exists. Numerical experiments show that the sources need to stay close to the boundary, and there is an optimal distance. Based on the maximum principle, a posteriori error can be monitored on the boundary to seek the optimal fictitious boundary location. Other topics discussed include the origin of the MFS, the equivalence between the MFS and the Trefftz collocation method, effective condition number, nonsingular MFS, and solving ill-posed and inverse problems.

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.

We present a quantum interior point method with worst case running time $\widetilde{O}(\frac{n^{2.5}}{\xi^{2}} \mu \kappa^3 \log (1/\epsilon))$ for SDPs and $\widetilde{O}(\frac{n^{1.5}}{\xi^{2}} \mu \kappa^3 \log (1/\epsilon))$ for LPs, where the output of our algorithm is a pair of matrices $(S,Y)$ that are $\epsilon$-optimal $\xi$-approximate SDP solutions. The factor $\mu$ is at most $\sqrt{2}n$ for SDPs and $\sqrt{2n}$ for LP's, and $\kappa$ is an upper bound on the condition number of the intermediate solution matrices. For the case where the intermediate matrices for the interior point method are well conditioned, our method provides a polynomial speedup over the best known classical SDP solvers and interior point based LP solvers, which have a worst case running time of $O(n^{6})$ and $O(n^{3.5})$ respectively. Our results build upon recently developed techniques for quantum linear algebra and pave the way for the development of quantum algorithms for a variety of applications in optimization and machine learning., Comment: 32 pages

Excessive synchronizations of neurons in the brain networks can be a reason for some episodic disorders such as epilepsy. In this paper, we simulate neural dynamic models and their synchronizations numerically by a new numerical algorithm. In order to overcome the complexity of the problem, a suitable combination of the Legendre spectral element method and operator splitting technique is proposed to convert a complex system of partial differential equations into sparse linear algebraic systems. The simulations are explored in different aspects such as accuracy, computing the wavefront and angular speeds, computing time, the condition number of obtained algebraic systems to demonstrate the proposed scheme effectiveness. The numerical simulations and comparisons confirm the method is suitable in terms of accuracy and speed.

Considering the importance of damage for the structural performance and for decreasing the identification error, this paper proposes an optimal sensor placement method based on a weighted standard deviation norm (WSDN) index. The standard deviation of the identified damage parameters is solved using the series expansion theory and probabilistic method to quantify the effect of a measurement error on damage identification. The damage estimation weight (DEW) index, which can reflect the importance of each element in the structural capabilities, is established based on a performance-damage curve. A significant DEW for a specified element indicates that the element is important for the structure and that its identification error should be small. The WSDN index is obtained from the Hadamard product of the standard deviations (SDs) and DEWs. Thus, the identification error of the entire structure is measured using the weighting coefficient. The optimal sensor placement (OSP) procedure is performed by minimizing the WSDN index. The proposed method can clearly decrease the uncertainties of the identification results for the important elements. Other OSP criteria, including the condition number, information entropy, and standard deviation norm, which aim to decrease the identification error, are discussed in this paper for comparison with the proposed method. Two numerical examples and an experiment, which pertain to the deformation performance, buckling features, and dynamic characteristics, are discussed to verify the advantages of the proposed method.

We show that a matrix A satisfying ‖ exp ⁡ ( t A ) ‖ ⩽ K for all t ⩾ 0 can be transformed to a block-diagonal form such that the condition numbers of all the diagonal blocks and the condition number of the transformation matrix depend only on K and the matrix size. This result is useful for the analysis of long-time simulation accuracy of numerical schemes.

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.

In this paper, three meshless methods are proposed to solve boundary value problems. The special purpose Trefftz function method, the method of fundamental solutions and the symmetry method of fundamental solutions are compared. We considered six numerical examples for harmonic and biharmonic problems as a flow through the cylindrical fibers arranged in a regular square array, deflection of a uniformly loaded square plate and torsion of a bar. The boundary value problems defined for a repeating element of the domain are solved by use of the collocation technique. The accuracy and stability of compared methods are investigated. Root mean square error on the boundary and condition number of the matrix are presented as functions of a number of collocation points.

In this paper, the technique of the Stable Generalized Finite Element Method (SGFEM) is applied to the numerically constructed functions of the Generalized Finite Element Method with Global-Local Enrichments (GFEMgl). The application of the resulting approach, named SGFEMgl, is expanded here to 2-D quasi-static crack propagation problems. Crack growth is performed by a two-scale strategy, using local problems generated at each propagation step – whose solutions enrich a single global problem defined on a coarse mesh. Stress Intensity Factors (SIFs) computed along crack growth, strain energy measures, performance in blending elements and the condition number are used to study the accuracy and conditioning of SGFEMgl. The method is compared with the standard GFEMgl. Numerical experiments demonstrate remarkable accuracy of SGFEMgl in linear elastic fracture mechanics problems, considering crack opening modes I and II. Convergence rates analyses also show the superiority of the method, especially with the use of geometrical enrichments.

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.

For Laplace's equation in a bounded simply-connected domain Ω in 3D, the method of fundamental solutions (MFS) is studied in this paper. Although some numerical computations can be found in Chen et al. [10] , the theoretical analysis is much behind (Li [23] only for unit sphere Ω). Our efforts are devoted to exploring a strict error analysis of the MFS. The error bounds are derived, and the optimal polynomial convergence rates can be achieved. Numerical experiments are carried out to support the analysis made, and several useful locations of source nodes are investigated numerically. The analysis in this paper may lay a theoretical basis of the MFS for 3D problems, as Bogomolny [8] and [24] for 2D problems. Besides, the method of particular solutions (MPS) in [26] is also studied by using the spherical harmonic functions (SHF). The optimal polynomial convergence rates and the exponential growth of condition number (Cond) are obtained. The source nodes are located based on the abscissas of quadrature rules on surfaces; they are “grid-like”. Since most of 3D problems, in reality, can not be simplified to 2D problems, and since the MFS has more advantages for 3D problems in algorithm simplicity and wide application, the study in this paper is essential and important to the MFS.

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.

The interpolating boundary element-free method (IBEFM) is a direct solution method of the meshless boundary integral equation method, which has high efficiency and accuracy. The IBEFM is developed based on the interpolating moving least-squares (IMLS) method and the boundary integral equation method. Since the shape function of the IMLS method satisfies the interpolation characteristics, the IBEFM can directly and accurately impose the essential boundary conditions, which overcomes the shortcomings of the original boundary element-free method in enforcing the essential boundary approximately. This paper will study the error estimations of the IBEFM for two-dimensional potential problems and the relationship between the errors and the influence radius and the condition number of the coefficient matrix. Two numerical examples are presented to verify the correctness of the theoretical results in this paper.

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.

We derived two adaptive choices for the nonnegative parameter of the Hager-Zhang conjugate gradient method. The first was achieved by minimizing the Frobenius condition number of the search direction matrix and the other by minimizing the difference between the smallest and the largest singular value. Global convergence is based on an appropriate assumption. Preliminary numerical results demonstrate the efficiency of the two adaptive choices.

SimRank is popularly used for evaluating similarities between nodes in a graph. Though some recent work has transformed the SimRank into a linear system which can be solved by using conjugate gradient (CG) algorithm. However, the diagonal preconditioner used in the algorithm still left some room for improvement. There is no work showing what should be an optimal preconditioner for the linear system. For such a sake, in this paper, we theoretically study the preconditioner problem and propose a polynomial preconditioner which can improve the computation speed significantly. In our investigation, we also modify the original linear system to adapt to all situations of the graph. We further prove that the condition number of a polynomial preconditioned matrix is bounded in a narrow interval. It implies that the new preconditioner can effectively accelerate the convergence rate of the CG algorithm. The experimental results show the proposed algorithm outperforms the state-of-the-art algorithms for the all-pairs SimRank computation.

The approximation accuracy of the wavelet spectral method for the fractional PDEs is sensitive to the order of the fractional derivative and the boundary condition of the PDEs. In order to overcome the shortcoming, an interval Shannon-Cosine wavelet based on the point-symmetric extension is constructed, and the corresponding spectral method on the fractional PDEs is proposed. In the research, a power function of cosine function is introduced to modulate Shannon function, which takes full advantage of the waveform of the Shannon function to ensure that many excellent properties can be satisfied such as the partition of unity, smoothness, and compact support. And the interpolative property of Shannon wavelet is held at the same time. Then, based on the point-symmetric extension and the general variational theory, an interval Shannon-Cosine wavelet is constructed. It is proved that the first derivative of the approximated function with this interval wavelet function is continuous. At last, the wavelet spectral method for the fractional PDEs is given by means of the interval Shannon-Cosine wavelet. By means of it, the condition number of the discrete matrix can be suppressed effectively. Compared with Shannon and Shannon-Gabor wavelet quasi-spectral methods, the novel scheme has stronger applicability to the shockwave appeared in the solution besides the higher numerical accuracy and efficiency.

This study aimed to provide a calibration criterion based on the condition number (Cond, Q) of the basis material matrix (BMM) to optimize experimental performance of basis of material decomposition (BMD) results. Cond(Q) was first elaborated theoretically and then phantom studies, including the possible influence of a number of experimental parameters, such as X-ray spectrum, the number of energy bins and the width of the energy bins, were performed to validate the criterion. In the BMD phantom study, the quantitative relationship between the proposed criterion and BMD accuracy was explored. Results showed that the proposed criterion was negatively correlated to BMD accuracy, and each of the experimental parameters influenced the criterion and BMD accuracy in a similar pattern. In conclusion Cond(Q) can be used to optimize experimental configurations of BMD.

In remote sensing data assimilation, inverse methods are often used to retrieve the boundary conditions from some of the observations in the interior scanning region. Needless to say, the inverse boundary value problem (IBVP) is ill-conditioned in general. Ultimately, the data assimilation must include mechanisms that enable them to overcome the numerical instability for solving IBVP. In this paper, we begin by studying the behavior of ill-conditioned IBVP, and find that the condition number varies with the number of the observations and distribution locations of the observations. Next, we define the number of equivalent independent equations as a novel measurement of ill-conditioning of a problem, which can measure the degree of bad conditions. Furthermore, the novel measure can answer how many additional observations are needed to stabilize the retrieving problem, and where additional observations are fixed up. Finally, we illustrate the proposed methodology by applying it to the study of precipitation data assimilation, with a particular emphasis on the analysis of the effect of the number of observations and their distribution locations. The new methodology appears to be particularly efficient in tackling the instability of the retrieving problem in data assimilation.

The governing equation of the stochastic Galerkin method can be formulated as a generalized Sylvester equation. Therefore, developing solvers for it is attracting a lot of attention from the uncertainty quantification community. In this regard Krylov subspace based iterative solvers, that are used for standard linear systems are being used for the generalized Sylvester equations as well. This is achieved by converting the generalized Sylvester equation to a standard linear system using the Kronecker product. Accordingly the residual norm is used as a stopping criterion for the iterations, and the condition number of linear systems is used for the generalized Sylvester equations as well. For a linear system a small residual norm implies a small backward error, and hence using residual norm as a stopping criterion is justified. In this work we prove that this need not be the case for the generalized Sylvester equation. We introduce two definitions for the backward error, and then derive an upper bound on each of them. We also verify the predictions of the analysis using numerical experiments. For the special case of the stochastic Galerkin method we show that the upper bound on the backward error can be computed with minimal computational overhead, and hence it can be used as a stopping criterion in the iterative solvers. For the matrices stemming from the stochastic Galerkin method we numerically demonstrate that the actual backward error can be up to 3 orders of magnitude higher than the relative residual. Finally by taking into account the structure of the equation we derive an expression for the condition number, and discuss an algorithm for its computation in the special case of the stochastic Galerkin method.