𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The concept of effective method applied to computational problems of linear algebra

✍ Scribed by Oliver Aberth

Publisher
Elsevier Science
Year
1971
Tongue
English
Weight
474 KB
Volume
5
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

A classification of computational problems is proposed which may have applications in numerical analysis. The classification utilizes the concept of effective method, which has been employed in treating decidability questions within the field of computable numbers. A problem is effectively soluble or effectively insoluble according as there is or there is not an effective method of solution. Roughly speaking~ effectively insoluble computational problems are those whose general solution is restricted by an intrinsic and unavoidable computational difficulty. Some standard problems of linear algebra are analyzed to determine their type.

πŸ“œ SIMILAR VOLUMES

The Computational Complexity of Some Pro
The Computational Complexity of Some Problems of Linear Algebra
✍ Jonathan F Buss; Gudmund S Frandsen; Jeffrey O Shallit πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 330 KB

We consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R. Let x 1 , x 2 , ..., x t be variables. Given a matrix M=M(x 1 , x 2 , ..., x t ) with entries chosen from E \_ [x 1 , x 2 , ..., x t ], we want to determine maxrank S (M)=