Loading...
Please wait, while we are loading the content...
Similar Documents
Computational complexity and numerical stability of linear problems (2009).
| Content Provider | CiteSeerX |
|---|---|
| Author | Holtz, Olga Shomron, Noam |
| Abstract | We survey classical and recent developments in numerical linear algebra, focusing on two issues: computational complexity, or arithmetic costs, and numerical stability, or performance under roundoff error. We present a brief account of the algebraic complexity theory as well as the general error analysis for matrix multiplication and related problems. We emphasize the central role played by the matrix multiplication problem and discuss historical and modern approaches to its solution. 1 Computational complexity of linear problems In algebraic complexity theory one is often interested in the number of arithmetic operations required to perform a given computation. This is called the total (arithmetic) complexity of the computation. 1 Moreover, it is often appropriate to count only multiplications (and divisions), but not additions or multiplications by fixed scalars. These notions can be formalized [BCS97, Definition 4.7]. For now, let us invoke Notation. Let F be a field, A be a F-algebra, and ϕ ∈ A be a function. The total arithmetic |
| File Format | |
| Publisher Date | 2009-01-01 |
| Access Restriction | Open |
| Subject Keyword | Computational Complexity Linear Problem Numerical Stability Algebraic Complexity Theory Brief Account Roundoff Error Recent Development Modern Approach Fixed Scalar Related Problem Numerical Linear Algebra Matrix Multiplication Problem Central Role Matrix Multiplication Arithmetic Operation Arithmetic Cost General Error Analysis |
| Content Type | Text |
