Search

In this paper, we propose a new approach to justify a roundoff error impact on the accuracy of the linear least squares (LS) solution using QR decomposition. This decomposition is widely employed to invert a matrix in the linear detector of the multi-user multi-antenna receiver. Compared to existing numerical results, the suggested stochastic bound is far closer to actual errors. It was put through a half-precision format test and verified in real-world scenarios generated by the Quadriga 2.0 tool and in random randsvd ensemble. The results of experiments show that our method predicts errors that are extremely similar to those observed in simulations. The suggested method can be used to examine the roundoff error in many other applications that require matrix inverse operations.

The paper considers the numerical stability of the backward recurrence algorithm (BRalgorithm) for computing approximants of the continued fraction with complex elements. The new method establishes sufficient conditions for the numerical stability of this algorithm and the error bounds of the calculation of the nth approximant of the continued fraction with complex elements. It follows from the obtained conditions that the numerical stability of the algorithm depends not only on the rounding errors of the elements and errors of machine operations but also on the value sets and the element sets of the continued fraction. The obtained results were used to study the numerical stability of the BR-algorithm for computing the approximants of the continued fraction expansion of the ratio of Horn's confluent functions H7. Bidisc and bicardioid regions are established, which guarantee the numerical stability of the BR-algorithm. The obtained result is applied to the study of the numerical stability of computing approximants of the continued fraction expansion of the ratio of Horn's confluent function H7 with complex parameters. In addition, the analysis of the relative errors arising from the computation of approximants using the backward recurrence algorithm, the forward recurrence algorithm, and Lenz's algorithm is given. The method for studying the numerical stability of the BR-algorithm proposed in the paper can be used to study the numerical stability of the branched continued fraction expansions and numerical branched continued fractions with elements in angular and parabolic domains. [ABSTRACT FROM AUTHOR]

Roundoff errors often disrupt interpolation methods for time-fractional equations, potentially causing suboptimal convergence or even failure. These issues primarily result from catastrophic cancellations. To address this, we introduce a novel framework for computing coefficients in standard and fast interpolation methods on nonuniform meshes. We propose δ -cancellation and associated threshold conditions to prevent such cancellations. If the thresholds aren't met, a Taylor expansion technique can be applied. Numerical experiments demonstrate our method's accuracy, on par with the Gauss–Kronrod quadrature, but significantly more efficient, allowing for extensive simulations with hundreds of thousands of time steps. [ABSTRACT FROM AUTHOR]

In this paper, we consider some numerical aspects of branched continued fractions as special families of functions to represent and expand analytical functions of several complex variables, including generalizations of hypergeometric functions. The backward recurrence algorithm is one of the basic tools of computation approximants of branched continued fractions. Like most recursive processes, it is susceptible to error growth. Each cycle of the recursive process not only generates its own rounding errors but also inherits the rounding errors committed in all the previous cycles. On the other hand, in general, branched continued fractions are a non-linear object of study (the sum of two fractional-linear mappings is not always a fractional-linear mapping). In this work, we are dealing with a confluent branched continued fraction, which is a continued fraction in its form. The essential difference here is that the approximants of the continued fraction are the so-called figure approximants of the branched continued fraction. An estimate of the relative rounding error, produced by the backward recurrence algorithm in calculating an nth approximant of the branched continued fraction expansion of Horn's hypergeometric function H4, is established. The derivation uses the methods of the theory of branched continued fractions, which are essential in developing convergence criteria. The numerical examples illustrate the numerical stability of the backward recurrence algorithm. [ABSTRACT FROM AUTHOR]

Geometric predicates are at the core of many algorithms, such as the construction of Delaunay triangulations, mesh processing and spatial relation tests. These algorithms have applications in scientific computing, geographic information systems and computer-aided design. With floating-point arithmetic, these geometric predicates can incur round-off errors that may lead to incorrect results and inconsistencies, causing computations to fail. This issue has been addressed using a combination of exact arithmetic for robustness and floating-point filters to mitigate the computational cost of exact computations. The implementation of exact computations and floating-point filters can be a difficult task, and code generation tools have been proposed to address this. We present a new C++ meta-programming framework for the generation of fast, robust predicates for arbitrary geometric predicates based on polynomial expressions. We combine and extend different approaches to filtering, branch reduction, and overflow avoidance that have previously been proposed. We show examples of how this approach produces correct results for data sets that could lead to incorrect predicate results with naive implementations. Our benchmark results demonstrate that our implementation surpasses state-of-the-art implementations. [ABSTRACT FROM AUTHOR]

In this work, a robust and rigorous procedure for roots calculation and selection for a Cubic Equation of State is presented. Roundoff errors are detected and corrected with a simple test in addition to an iterative procedure, adapted from the fixed-point method. The new approach applies some properties of Cardano's formulation to find the appropriate phase root of the cubic equation. Furthermore, to find out the actual physical state of the system, when the polynomial function presents only one root, special properties of the second derivative of the cubic polynomial in compressibility factor form and its partial derivative with respect to pressure are analyzed on a rigorous thermodynamic basis. These results are applied to outline an efficient algorithm to calculate the saturation pressure of pure components, which is independent of an accurate initial estimate and integrates bisection, successive substitution, and Newton–Raphson methods to find the correct value in few iterations. [ABSTRACT FROM AUTHOR]

Large-scale optimization problems arising from the discretization of problems involving PDEs sometimes admit solutions that can be well approximated by low-rank matrices. In this paper, we will exploit this low-rank approximation property by solving the optimization problem directly over the set of low-rank matrices. In particular, we introduce a new multilevel algorithm, where the optimization variable is constrained to the Riemannian manifold of fixed-rank matrices. In contrast to most other multilevel algorithms, where the rank is chosen adaptively on each level in order to control the perturbation due to the low-rank truncation, we can keep the ranks (and thus the computational complexity) fixed throughout the iterations. Furthermore, classical implementations of line searches based on Wolfe conditions enable computing a solution where the numerical accuracy is limited to about the square root of the machine epsilon. Here, we propose an extension to Riemannian manifolds of the line search of Hager and Zhang, which uses approximate Wolfe conditions that enable computing a solution on the order of the machine epsilon. Numerical experiments demonstrate the computational efficiency of the proposed framework. [ABSTRACT FROM AUTHOR]

The rapid development of digital computer hardware and software has had a dramatic influence on mathematics, and contrary. The advanced hardware and modern sophistical software such as computer visualization, symbolic computation, computer-assisted proofs, multi-precision arithmetic and powerful libraries, have provided resolving many open problems, a huge very difficult mathematical problems, and discovering new patterns and relationships, far beyond a human capability. In the first part of the paper we give a short review of some typical mathematical problems solved by computer tools. In the second part we present some new original contributions, such as intriguing consequence of the presence of roundoff errors, distribution of zeros of random polynomials, dynamic study of zero-finding methods, a new three-point family of methods for solving nonlinear equations and two algorithms for the inclusion of a simple complex zero of a polynomial. [ABSTRACT FROM AUTHOR]

For large-scale problems, how to establish an algorithm with high accuracy and stability is particularly important. In this paper, the Householder bidiagonalization total least squares (HBITLS) algorithm and nonlinear iterative partial least squares for total least squares (NIPALS-TLS) algorithm were established, by which the same approximate TLS solutions was obtained. In addition, the propagation of the roundoff error for the process of the HBITLS algorithm was analyzed, and the mixed forward-backward stability of these two algorithms was proved. Furthermore, an upper bound of roundoff error was derived, which presents a more detailed and clearer approximation of the computed solution.

A long-standing problem related to floating-point implementation of numerical programs is to provide efficient yet precise analysis of output errors. We present a framework to compute lower bounds on largest absolute roundoff errors, for a particular rounding model. This method applies to numerical programs implementing polynomial functions with box constrained input variables. Our study is based on three different hierarchies, relying respectively on generalized eigenvalue problems, elementary computations, and semidefinite programming (SDP) relaxations. This is complementary of over-approximation frameworks, consisting of obtaining upper bounds on the largest absolute roundoff error. Combining the results of both frameworks allows one to get enclosures for upper bounds on roundoff errors. The under-approximation framework provided by the third hierarchy is based on a new sequence of convergent robust SDP approximations for certain classes of polynomial optimization problems. Each problem in this hierarchy can be solved exactly via SDP. By using this hierarchy, one can provide a monotone nondecreasing sequence of lower bounds converging to the absolute roundoff error of a program implementing a polynomial function, applying for a particular rounding model. We investigate the efficiency and precision of our method on nontrivial polynomial programs coming from space control, optimization, and computational biology. [ABSTRACT FROM AUTHOR]

The algorithm by Al-Mohy and Higham (2011) [2] computes an approximation to e A b for given A and b , where A is an n -by- n matrix and b is, for example, a vector of dimension n . It uses a scaling together with a truncated Taylor series approximation to the exponential of the scaled matrix. In this paper, a method is developed for estimating the roundoff error of the computed solution. An asymptotic expansion of this error for small values of the unit roundoff is the basis of the method. The roundoff error is further expressed in terms of sums of rounding errors, which occur during the computation. A second approximation to e A b , which is computed with a lower precision than the first one, is used to evaluate these rounding errors in practice. The result is an upper bound on the normwise relative roundoff error. Further, an algorithm is proposed for computing the error bound. The cost for performing this algorithm depends on the type of problem and the accuracy, which is required for the error estimate. In case that all computations are performed with standard precisions, this cost can be expressed in terms of the number of computed matrix-vector products and is bounded from above by two times the cost for computing e A b . [ABSTRACT FROM AUTHOR]

Numerical software, common in scientific computing or embedded systems, inevitably uses a finite-precision approximation of the real arithmetic in which most algorithms are designed. In many applications, the roundoff errors introduced by finite-precision arithmetic are not the only source of inaccuracy, and measurement and other input errors further increase the uncertainty of the computed results. Adequate tools are needed to help users select suitable data types and evaluate the provided accuracy, especially for safety-critical applications. We present a source-to-source compiler called Rosa that takes as input a real-valued program with error specifications and synthesizes code over an appropriate floating-point or fixed-point data type. The main challenge of such a compiler is a fully automated, sound, and yet accurate-enough numerical error estimation. We introduce a unified technique for bounding roundoff errors from floating-point and fixed-point arithmetic of various precisions. The technique can handle nonlinear arithmetic, determine closed-form symbolic invariants for unbounded loops, and quantify the effects of discontinuities on numerical errors. We evaluate Rosa on a number of benchmarks from scientific computing and embedded systems and, comparing it to the state of the art in automated error estimation, show that it presents an interesting tradeoff between accuracy and performance. [ABSTRACT FROM AUTHOR]