Some computational problems in linear algebra as hard as matrix multiplication期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Some computational problems in linear algebra as hard as matrix multiplication

Authors:	Peter Bürgisser Marek Karpinski Thomas Lickteig

Affiliation:	1. Institut für Informatik, Universit?t Bonn, D-5300, Bonn 1 2. International Computer Science Institute, 94704, Berkeley, CA 3. Fachbereich Mathematik, Universit?t Tübingen, D-7400, Tübingen

Abstract:	We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are: KER _n: Compute a basis of the kernel for a givenn×n-matrix, OGB _n: Find an invertible matrix that transforms a given symmetricn×n-matrix (quadratic form) into diagonal form, SPR _n: Find a sparse representation of a givenn×n-matrix.

Keywords:
本文献已被 SpringerLink 等数据库收录！