BibSonomy publications for /user/ejrTue Oct 09 07:04:05 CEST 2007Livermore, CAThird Bay Area Scientific Computing DayMarchParallel Bipartite Matching for Sparse Matrix Computation2002bascd combinatorialoptimization parallelalgorithms sparsematrix Tue Oct 09 07:04:05 CEST 2007IEEE-754r revision meetingAugustException Handling Interfaces, Implementations, and Evaluation2002floatingpoint ieee754 Tue Oct 09 07:04:05 CEST 2007SIAM Conference on Computational Science and EngineeringFebruaryParallel Bipartite Matching for Sparse Matrix Computations2003combinatorialoptimization parallelalgorithms siam sparsematrix Tue Oct 09 07:04:05 CEST 2007SIAM Annual MeetingJunePractical Alternatives for Parallel Pivoting2003linearalgebra siam sparsematrix Tue Oct 09 07:04:05 CEST 2007SIAM Parallel Processing for Scientific ComputingfebParallel Weighted Bipartite Matching and Applications2004combinatorialoptimization parallelalgorithms siam sparsematrix Tue Oct 09 07:04:05 CEST 2007SIAM Workshop on Combinatorial Scientific ComputingfebSparse Data Structures for Weighted Bipartite Matching2004combinatorialoptimization siam sparsematrix Tue Oct 09 07:04:05 CEST 2007SIAM Conference on Computational Science and EngineeringfebParallel Combinatorial Computing and Sparse Matrices2005combinatorialoptimization parallelalgorithms siam sparsematrix Tue Oct 09 07:04:05 CEST 2007{ARITH}'05Modern Language Tools and {754R}2005floatingpoint ieee754 Tue Oct 09 07:04:05 CEST 2007Robert C. Thompson Matrix MeetingNovemberThe Future of {LAPACK} and {ScaLAPACK}2005lapack softwareengineering We are planning new releases of the widely used LAPACK and ScaLAPACK numerical linear algebra libraries. Based on an on-going user survey (http://www.netlib.org/lapack-dev) and research by many people, we are proposing the following improvements: Faster algorithms (including better numerical methods, memory hierarchy optimizations, parallelism, and automatic performance tuning to accomodate new architectures), more accurate algorithms (including better numerical methods, and use of extra precision), expanded functionality (including updating and downdating, new eigenproblems, etc. and putting more of LAPACK into ScaLAPACK), and improved ease of use (friendlier interfaces in multiple languages). To accomplish these goals we are also relying on better software engineering techniques and contributions from collaborators at many institutions. This is joint work with Jack Dongarra.Tue Oct 09 07:04:05 CEST 2007Livermore, CASeventh Bay Area Scientific Computing DayMarchMaking Static Pivoting Dependable2006bascd linearalgebra sparsematrix For sparse LU factorization, dynamic pivoting tightly couples symbolic and numerical computation. Dynamic structural changes limit parallel scalability. Demmel and Li use static pivoting in distributed SuperLU for performance, but intentionally perturbing the input may lead silently to erroneous results. Are there experimentally stable static pivoting heuristics that lead to a dependable direct solver? The answer is currently a qualified yes. Current heuristics fail on a few systems, but all failures are detectable. Tue Oct 09 07:04:05 CEST 2007Stanford, CAStanford 50 -- Eighth Bay Area Scientific Computing DayMarchPrecise Solutions for Overdetermined Least Squares Problems2007bascd leastsquares Linear least squares (LLS) fitting is the most widely used data modeling technique and is included in almost every data analysis system (e.g. spreadsheets). These software systems often give no feedback on the conditioning of the LLS problem or the floating-point calculation errors present in the solution. With limited use of extra precision, we can eliminate these concerns for all but the most ill-conditioned LLS problems. Our algorithm provides either a solution and residual with relatively tiny error or a notice that the LLS problem is too ill-conditioned.Tue Oct 09 07:03:39 CEST 2007Umeå, SwedenPARA'06: State-of-the-Art in Scientific and Parallel ComputingJuneProspectus for the Next LAPACK and ScaLAPACK Libraries2006lapack LAPACK and ScaLAPACK are widely used software libraries for numerical linear algebra. There have been over 68M web hits at www.netlib.org for the associated libraries LAPACK, ScaLAPACK, CLAPACK and LAPACK95. LAPACK and ScaLAPACK are used to solve leading edge science problems and they have been adopted by many vendors and software providers as the basis for their own libraries, including AMD, Apple (under Mac OS X), Cray, Fujitsu, HP, IBM, Intel, NEC, SGI, several Linux distributions (such as Debian), NAG, IMSL, the MathWorks (producers of MATLAB), Interactive Supercomputing, and PGI. Future improvements in these libraries will therefore have a large impact on users.Tue Oct 09 07:02:59 CEST 2007SeptemberAlso issued as UCB//CSD-05-1414; expanded from SISC version172Benefits of IEEE-754 Features in Modern Symmetric Tridiagonal EigensolversLAPACK Working Note2005eigenvalue floatingpoint ieee754 lapack lawn Tue Oct 09 07:01:39 CEST 2007MayAlso issued as UCB/EECS-2007-77; sumbitted to TOMS.188Extra-precise iterative refinement for overdetermined least squares problemsLAPACK Working Note2007floatingpoint lapack lawn leastsquares We present the algorithm, error bounds, and numerical results for extra-precise iterative refinement applied to overdetermined linear least squares (LLS) problems. We apply our linear system refinement algorithm to Bj\"orck’s augmented linear system formulation of an LLS problem. Our algorithm reduces the forward normwise and componentwise errors to $O(\varepsilon)$ unless the system is too ill conditioned. In contrast to linear systems, we provide two separate error bounds for the solution $x$ and the residual $r$. The refinement algorithm requires only limited use of extra precision and adds only $O(mn)$ work to the $O(mn^2)$ cost of QR factorization for problems of size m-by-n. The extra precision calculation is facilitated by the new extended-precision BLAS standard in a portable way, and the refinement algorithm will be included in a future release of LAPACK and can be extended to the other types of least squares problems.Tue Oct 09 07:01:39 CEST 2007FebruaryAlso issued as UCB//CSD-05-1414, UT-CS-05-547, and LBNL-56965; expanded from TOMS version165Error bounds from extra-precise iterative refinementLAPACK Working Note2005floatingpoint lapack lawn linearalgebra Tue Oct 09 07:01:39 CEST 2007FebruaryAlso issued as UT-CS-07-592181Prospectus for the Next {LAPACK} and {ScaLAPACK} LibrariesLAPACK Working Note2007lapack lawn Tue Oct 09 06:59:39 CEST 200717th IEEE Symposium on Computer Arithmetic (ARITH'05)Arithmetic Interactions: From Hardware to Applications2005floatingpoint ieee754 The entire process of creating and executing applications that solve interesting problems with acceptable cost and accuracy involves a complex interaction among hardware, system software, programming environments, mathematical software libraries, and applications software, all mediated by standards for arithmetic, operating systems, and programming environments. This panel will discuss various issues arising among these various contending points of view, sometimes from the point of view of issues raised during the current IEEE 754R standards revision effort.Tue Oct 09 06:58:21 CEST 2007San Diego, CAParallel and Distributed Methods for Image Processing199--210Efficient {SIMD} evaluation of image processing programs31661997imagealgebra parallelalgorithms spie SIMD parallel systems have been employed for image processing and computer vision applications since their inception. This paper describes a system in which parallel programs are implemented using a machine-independent, retargetable object library that provides SIMD execution on the Lockheed Martin PAL-I SIMD parallel processor. Programs' performance on this machine is improved through on-the-fly execution analysis and scheduling. We describe the relevant elements of the system structure, the general scheme for execution analysis, and the current cost model for scheduling.Tue Oct 09 06:57:46 CEST 2007ACM Transactions on Mathematical SoftwareJune2325--351Error bounds from extra-precise iterative refinement322006acm floatingpoint lapack linearalgebra toms We present the design and testing of an algorithm for iterative refinement of the solution of linear equations where the residual is computed with extra precision. This algorithm was originally proposed in 1948 and analyzed in the 1960s as a means to compute very accurate solutions to all but the most ill-conditioned linear systems. However, two obstacles have until now prevented its adoption in standard subroutine libraries like LAPACK: (1) There was no standard way to access the higher precision arithmetic needed to compute residuals, and (2) it was unclear how to compute a reliable error bound for the computed solution. The completion of the new BLAS Technical Forum Standard has essentially removed the first obstacle. To overcome the second obstacle, we show how the application of iterative refinement can be used to compute an error bound in any norm at small cost and use this to compute both an error bound in the usual infinity norm, and a componentwise relative error bound.Tue Oct 09 06:57:00 CEST 2007SIAM Journal on Scientific Computing51613--1633Benefits of {IEEE-754} Features in Modern Symmetric Tridiagonal Eigensolvers282006eigenvalue floatingpoint ieee754 siam sisc Bisection is one of the most common methods used to compute the eigenvalues of symmetric tridiagonal matrices. Bisection relies on the Sturm count: For a given shift sigma, the number of negative pivots in the factorization $T - \sigma I = LDL^T$ equals the number of eigenvalues of T that are smaller than sigma. In IEEE-754 arithmetic, the value $\infty$ permits the computation to continue past a zero pivot, producing a correct Sturm count when $T$ is unreduced. Demmel and Li showed [IEEE Trans. Comput., 43 (1994), pp. 983–992] that using $\infty$ rather than testing for zero pivots within the loop could significantly improve performance on certain architectures. When eigenvalues are to be computed to high relative accuracy, it is often preferable to work with $LDL^T$ factorizations instead of the original tridiagonal $T$. One important example is the MRRR algorithm. When bisection is applied to the factored matrix, the Sturm count is computed from $LDL^T$ which makes differential stationary and progressive qds algorithms the methods of choice. While it seems trivial to replace $T$ by $LDL^T$, in reality these algorithms are more complicated: In IEEE-754 arithmetic, a zero pivot produces an overflow followed by an invalid exception (NaN, or "Not a Number") that renders the Sturm count incorrect. We present alternative, safe formulations that are guaranteed to produce the correct result. Benchmarking these algorithms on a variety of platforms shows that the original formulation without tests is always faster provided that no exception occurs. The transforms see speed-ups of up to 2.6x over the careful formulations. Tests on industrial matrices show that encountering exceptions in practice is rare. This leads to the following design: First, compute the Sturm count by the fast but unsafe algorithm. Then, if an exception occurs, recompute the count by a safe, slower alternative. The new Sturm count algorithms improve the speed of bisection by up to 2x on our test matrices. Furthermore, unlike the traditional tiny-pivot substitution, proper use of IEEE-754 features provides a careful formulation that imposes no input range restrictions.