23 results
Now showing1 - 10 of 23
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Adaptive and efficient algorithm for 2D orientation problemThis paper is concerned with a robust geometric predicate for the 2D orientation problem. Recently, a fast and accurate floating-point summation algorithm is investigated by Rump, Ogita and Oishi, which provably outputs a result faithfully rounded from the exact value of the summation of floating-point numbers. We optimize their algorithm for applying it to the 2D orientation problem which requires only a correct sign of a determinant of a 3×3 matrix. Numerical results illustrate that our algorithm works fairly faster than the state-of-the-art algorithm in various cases.Publicationtype: Journal Article39 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Iterative refinement for ill-conditioned linear systemsThis paper treats a linear equation Aυ = b, where A ∈ F n×n and b ∈ Fn. Here, F is a set of floating point numbers. Let u be the unit round-off of the working precision and κ(A) = ∥A∥∞∥A-1∥∞ be the condition number of the problem. In this paper, ill-conditioned problems with 1 < uκ(A) < ∞ are considered and an iterative refinement algorithm for the problems is proposed. In this paper, the forward and backward stability will be shown for this iterative refinement algorithm.Publicationtype: Journal Article31 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Accurate floating-point summation part II: Sign. Κ-Fold faithful and rounding to nearest(Society for Industrial & Applied Mathematics (SIAM), 2008-12-31); ; In Part II of this paper we first refine the analysis of error-free vector transformations presented in Part I. Based on that we present an algorithm fo r calculating the rounded-to-nearest result of s := σPi for a given vector of floating-point numbers pi. as well as algorithms for directed rounding. A special algorithm for computing the sign of s is given, also working for huge dimensions. Assume a floating-point working precision with relative round ing error unit eps. We define and investigate a Κ-fold faithful rounding of a real number r. Basically the result is stored in a vector Resv of Κ nonoverlapping floating-point numbers such that σ Resv approximates r with relative accuracy epsΚ, and replacing Resκ by its floating-point neighbors in Y. Resv forms a lower and upper bound for r. For a given vector of floating-point numbers with exact sums, we present an algorithm for calculating a Κ-fold faithful rounding of s using solely the working precision. Furthermore, an algorithm for calculating a faithfully rounded result of the sum of a vector of huge dimension is presented. Our algorithms are fast in terms of measured computing time because they allow good instruction-level parallelism, they neither require special operations such as access to mantissa or exponent. they contain no branch in the inner loop. nor do they require some extra precision. The only operations used are standard floating-point addition, subtraction, and multiplication in one working precision, for example, double precision. Certain c onstants used in the algorithms are proved to be optimal. © 2008 Society for Industrial and Applied Mathematics.Publicationtype: Journal Article48 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A parallel algorithm for accurate dot productParallel algorithms for accurate summation and dot product are proposed. They are parallelized versions of fast and accurate algorithms of calculating sum and dot product using error-free transformations which are recently proposed by Ogita et al. [T. Ogita, S.M. Rump, S. Oishi, Accurate sum and dot product, SIAM J. Sci. Comput. 26 (6) (2005) 1955-1988]. They have shown their algorithms are fast in terms of measured computing time. However, due to the strong data dependence in the process of their algorithms, it is difficult to parallelize them. Similarly to their algorithms, the proposed parallel algorithms in this paper are designed to achieve the results as if computed in K-fold working precision with keeping the fastness of their algorithms. Numerical results are presented showing the performance of the proposed parallel algorithm of calculating dot product.Publicationtype: Journal Article47 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Accurate matrix multiplication by using level 3 BLAS operationThis paper is concerned with an accurate computation of matrix multiplication. Recently, an accurate summation algorithm was developed by Rump, Ogita and Oishi. One of the key techniques of their method is a new type of error-free splitting. To use this strategy, we investigate a method of obtaining an accurate result of matrix multiplication by mainly using Level 3 BLAS operation. Finally, we present numerical examples showing the e ectiveness of the proposal algorithm.Publicationtype: Conference Paper31 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , 34 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Accurate floating-point summation part I: Faithful rounding(Society for Industrial & Applied Mathematics (SIAM), 2008); ; Given a vector of floating-point numbers with exact sum s, we present an algorithm for calculating a faithful rounding of s, i.e., the result is one of the immediate floating-point neighbors of s. If the sum a is a floating-point number, we prove that this is the result of our algorithm. The algorithm adapts to the condition number of the sum, i.e., it is fast for mildly conditioned sums with slowly increasing computing time proportional to the logarithm of the condition number. All statements are also true in the presence of underflow. The algorithm does not depend on the exponent range. Our algorithm is fast in terms of measured computing time because it allows good instructionlevel parallelism, it neither requires special operations such as access to mantissa or exponent, it contains no branch in the inner loop, nor does it require some extra precision: The only operations used are standard floating-point addition, subtraction, and multiplication in one working precision, for example, double precision. Certain constants used in the algorithm are proved to be optimal. © 2008 Society for Industrial and Applied Mathematics.Publicationtype: Journal Article45 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , 15 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , 56 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , 38