An $O(n^2\log^4 n \log \log n)$ Time Matrix Multiplication Algorithm Article Swipe

PDF

Yijie Han ·

YOU? · · 2016 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1612.04208

We show, for the input vectors $(a_0, a_1, ..., a_{n-1})$ and $(b_0, b_1, ..., b_{n-1})$, where $a_i$'s and $b_j$'s are real numbers, after $O(n\log^4 n)$ time preprocessing for each of them, the vector multiplication $(a_0, a_1, ..., a_{n-1})(b_0, b_1, ..., b_{n-1})^T $ can be computed in $O(\log^4 n \log \log n)$ time. This enables the matrix multiplication for two $n\times n$ matrices to be computed in $O(n^2 \log^4 n\log \log n)$ time.

Related Topics

Concepts

Binary logarithm Log-log plot Matrix multiplication Combinatorics Multiplication (music) Matrix (chemical analysis) Mathematics Arithmetic Physics Chemistry Quantum Quantum mechanics Chromatography

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/1612.04208
PDF: https://arxiv.org/pdf/1612.04208
OA Status: green
Cited By: 2
Related Works: 10
OpenAlex ID: https://openalex.org/W4367048734

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4367048734

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.1612.04208

Digital Object Identifier
Title: An $O(n^2\log^4 n \log \log n)$ Time Matrix Multiplication Algorithm

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2016

Year of publication
Publication date: 2016-12-10

Full publication date if available
Authors: Yijie Han

List of authors in order
Landing page: https://arxiv.org/abs/1612.04208

Publisher landing page
PDF URL: https://arxiv.org/pdf/1612.04208

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/1612.04208

Direct OA link when available
Concepts: Binary logarithm, Log-log plot, Matrix multiplication, Combinatorics, Multiplication (music), Matrix (chemical analysis), Mathematics, Arithmetic, Physics, Chemistry, Quantum, Quantum mechanics, Chromatography

Top concepts (fields/topics) attached by OpenAlex
Cited by: 2

Total citation count in OpenAlex
Citations by year (recent): 2023: 2

Per-year citation counts (last 5 years)
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4367048734
doi	https://doi.org/10.48550/arxiv.1612.04208
ids.doi	https://doi.org/10.48550/arxiv.1612.04208
ids.openalex	https://openalex.org/W4367048734
fwci
type	preprint
title	An $O(n^2\log^4 n \log \log n)$ Time Matrix Multiplication Algorithm
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10054
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9961000084877014
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1708
topics[0].subfield.display_name	Hardware and Architecture
topics[0].display_name	Parallel Computing and Optimization Techniques
topics[1].id	https://openalex.org/T12162
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9932000041007996
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Cellular Automata and Applications
topics[2].id	https://openalex.org/T12303
topics[2].field.id	https://openalex.org/fields/26
topics[2].field.display_name	Mathematics
topics[2].score	0.9925000071525574
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2605
topics[2].subfield.display_name	Computational Mathematics
topics[2].display_name	Tensor decomposition and applications
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C63553672
concepts[0].level	2
concepts[0].score	0.7403500080108643
concepts[0].wikidata	https://www.wikidata.org/wiki/Q581168
concepts[0].display_name	Binary logarithm
concepts[1].id	https://openalex.org/C195292467
concepts[1].level	3
concepts[1].score	0.6527523994445801
concepts[1].wikidata	https://www.wikidata.org/wiki/Q2091879
concepts[1].display_name	Log-log plot
concepts[2].id	https://openalex.org/C17349429
concepts[2].level	3
concepts[2].score	0.6523501873016357
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1049914
concepts[2].display_name	Matrix multiplication
concepts[3].id	https://openalex.org/C114614502
concepts[3].level	1
concepts[3].score	0.606661856174469
concepts[3].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[3].display_name	Combinatorics
concepts[4].id	https://openalex.org/C2780595030
concepts[4].level	2
concepts[4].score	0.5961780548095703
concepts[4].wikidata	https://www.wikidata.org/wiki/Q3860309
concepts[4].display_name	Multiplication (music)
concepts[5].id	https://openalex.org/C106487976
concepts[5].level	2
concepts[5].score	0.48899853229522705
concepts[5].wikidata	https://www.wikidata.org/wiki/Q685816
concepts[5].display_name	Matrix (chemical analysis)
concepts[6].id	https://openalex.org/C33923547
concepts[6].level	0
concepts[6].score	0.43620920181274414
concepts[6].wikidata	https://www.wikidata.org/wiki/Q395
concepts[6].display_name	Mathematics
concepts[7].id	https://openalex.org/C94375191
concepts[7].level	1
concepts[7].score	0.34948551654815674
concepts[7].wikidata	https://www.wikidata.org/wiki/Q11205
concepts[7].display_name	Arithmetic
concepts[8].id	https://openalex.org/C121332964
concepts[8].level	0
concepts[8].score	0.2110234498977661
concepts[8].wikidata	https://www.wikidata.org/wiki/Q413
concepts[8].display_name	Physics
concepts[9].id	https://openalex.org/C185592680
concepts[9].level	0
concepts[9].score	0.05921086668968201
concepts[9].wikidata	https://www.wikidata.org/wiki/Q2329
concepts[9].display_name	Chemistry
concepts[10].id	https://openalex.org/C84114770
concepts[10].level	2
concepts[10].score	0.0
concepts[10].wikidata	https://www.wikidata.org/wiki/Q46344
concepts[10].display_name	Quantum
concepts[11].id	https://openalex.org/C62520636
concepts[11].level	1
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q944
concepts[11].display_name	Quantum mechanics
concepts[12].id	https://openalex.org/C43617362
concepts[12].level	1
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q170050
concepts[12].display_name	Chromatography
keywords[0].id	https://openalex.org/keywords/binary-logarithm
keywords[0].score	0.7403500080108643
keywords[0].display_name	Binary logarithm
keywords[1].id	https://openalex.org/keywords/log-log-plot
keywords[1].score	0.6527523994445801
keywords[1].display_name	Log-log plot
keywords[2].id	https://openalex.org/keywords/matrix-multiplication
keywords[2].score	0.6523501873016357
keywords[2].display_name	Matrix multiplication
keywords[3].id	https://openalex.org/keywords/combinatorics
keywords[3].score	0.606661856174469
keywords[3].display_name	Combinatorics
keywords[4].id	https://openalex.org/keywords/multiplication
keywords[4].score	0.5961780548095703
keywords[4].display_name	Multiplication (music)
keywords[5].id	https://openalex.org/keywords/matrix
keywords[5].score	0.48899853229522705
keywords[5].display_name	Matrix (chemical analysis)
keywords[6].id	https://openalex.org/keywords/mathematics
keywords[6].score	0.43620920181274414
keywords[6].display_name	Mathematics
keywords[7].id	https://openalex.org/keywords/arithmetic
keywords[7].score	0.34948551654815674
keywords[7].display_name	Arithmetic
keywords[8].id	https://openalex.org/keywords/physics
keywords[8].score	0.2110234498977661
keywords[8].display_name	Physics
keywords[9].id	https://openalex.org/keywords/chemistry
keywords[9].score	0.05921086668968201
keywords[9].display_name	Chemistry
language	en
locations[0].id	pmh:oai:arXiv.org:1612.04208
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/1612.04208
locations[0].version	submittedVersion
locations[0].raw_type
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/1612.04208
locations[1].id	doi:10.48550/arxiv.1612.04208
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.1612.04208
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5091329448
authorships[0].author.orcid	https://orcid.org/0000-0003-1305-6815
authorships[0].author.display_name	Yijie Han
authorships[0].author_position	first
authorships[0].raw_author_name	Han, Yijie
authorships[0].is_corresponding	True
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/1612.04208
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	An $O(n^2\log^4 n \log \log n)$ Time Matrix Multiplication Algorithm
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10054
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9961000084877014
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1708
primary_topic.subfield.display_name	Hardware and Architecture
primary_topic.display_name	Parallel Computing and Optimization Techniques
related_works	https://openalex.org/W2035522910, https://openalex.org/W3099313426, https://openalex.org/W2005615533, https://openalex.org/W4287593139, https://openalex.org/W4243665620, https://openalex.org/W2057797376, https://openalex.org/W2090319426, https://openalex.org/W1529311266, https://openalex.org/W752783541, https://openalex.org/W2047234016
cited_by_count	2
counts_by_year[0].year	2023
counts_by_year[0].cited_by_count	2
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:1612.04208
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/1612.04208
best_oa_location.version	submittedVersion
best_oa_location.raw_type
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/1612.04208
primary_location.id	pmh:oai:arXiv.org:1612.04208
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/1612.04208
primary_location.version	submittedVersion
primary_location.raw_type
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/1612.04208
publication_date	2016-12-10
publication_year	2016
referenced_works_count	0
abstract_inverted_index.$	41
abstract_inverted_index.n	47
abstract_inverted_index.We	0
abstract_inverted_index.be	43, 63
abstract_inverted_index.in	45, 65
abstract_inverted_index.n$	60
abstract_inverted_index.of	29
abstract_inverted_index.to	62
abstract_inverted_index.and	10, 17
abstract_inverted_index.are	19
abstract_inverted_index.can	42
abstract_inverted_index.for	2, 27, 57
abstract_inverted_index.n)$	24, 50, 70
abstract_inverted_index.the	3, 31, 54
abstract_inverted_index.two	58
abstract_inverted_index....,	8, 13, 36, 39
abstract_inverted_index.This	52
abstract_inverted_index.\log	48, 49, 69
abstract_inverted_index.a_1,	7, 35
abstract_inverted_index.b_1,	12, 38
abstract_inverted_index.each	28
abstract_inverted_index.real	20
abstract_inverted_index.time	25
abstract_inverted_index.after	22
abstract_inverted_index.input	4
abstract_inverted_index.n\log	68
abstract_inverted_index.show,	1
abstract_inverted_index.them,	30
abstract_inverted_index.time.	51, 71
abstract_inverted_index.where	15
abstract_inverted_index.$(a_0,	6, 34
abstract_inverted_index.$(b_0,	11
abstract_inverted_index.$O(n^2	66
abstract_inverted_index.\log^4	67
abstract_inverted_index.matrix	55
abstract_inverted_index.vector	32
abstract_inverted_index.$a_i$'s	16
abstract_inverted_index.$b_j$'s	18
abstract_inverted_index.enables	53
abstract_inverted_index.vectors	5
abstract_inverted_index.$n\times	59
abstract_inverted_index.computed	44, 64
abstract_inverted_index.matrices	61
abstract_inverted_index.numbers,	21
abstract_inverted_index.$O(\log^4	46
abstract_inverted_index.a_{n-1})$	9
abstract_inverted_index.$O(n\log^4	23
abstract_inverted_index.b_{n-1})$,	14
abstract_inverted_index.b_{n-1})^T	40
abstract_inverted_index.a_{n-1})(b_0,	37
abstract_inverted_index.preprocessing	26
abstract_inverted_index.multiplication	33, 56
cited_by_percentile_year
corresponding_author_ids	https://openalex.org/A5091329448
countries_distinct_count	0
institutions_distinct_count	1
citation_normalized_percentile