A note on border rank
type: Item
instance of: scholarly article
title: A note on border rank
zbMATH Open document ID: 0539.68029
DOI: 10.1016/0020-0190(84)90023-1
author: Thomas Lickteig
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: Approximative bilinear algorithms play an important role in the investigation of the complexity of matrix multiplication. In this paper the lower bound \(rk<n,n,n>\geq(3/2)n^ 2+n/2-1\) for the border rank \((=\) approximative bilinear complexity) of the structural tensor \(<n,n,n>\) of \(n\times n\) matrix multiplication is given. This result is based on a description of the algebraic variety \(X_ r=\{t:rk t\leq r\}\) of tensors of border rank \(\leq r\) by a certain existential condition. As another application of the given description of \(X_ r\) it can be shown that larger matrix multiplications always have larger approximative bilinear complexity, i.e., \(rk<n_ 1,n_ 2,n_ 3><rk<n_ 1,n_ 2,n_ 3+1>.\)
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 3858404
zbMATH Keywords: computational complexity of bilinear forms
zbMATH Keywords: tensor rank
zbMATH Keywords: complexity of matrix multiplication
zbMATH Keywords: border rank
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90023-1
OpenAlex ID: W1997237738
cites work: \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
cites work: On the Asymptotic Complexity of Matrix Multiplication
cites work: Q4106341
cites work: Further Pathologies in Algebraic Geometry
cites work: Partial and Total Matrix Multiplication
cites work: Rank and optimal computation of generic tensors
cites work: Q5511421
description: scientific article; zbMATH DE number 3858404