• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Preprints
  • Parallel Heuristic Exploration for Additive Complexity Reduction in Fast Matrix Multiplication
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
November 17, 2026
Physicists Show How a Solvent Shapes the Response of Drug Molecules
Many drug molecules can switch between different three-dimensional shapes. Using a mathematical model of ibuprofen dissolved in supercritical CO₂, researchers from HSE University and the Institute of Solution Chemistry of the Russian Academy of Sciences have shown that the solvent can make these molecules appear to respond unusually slowly. The molecules themselves continue to change shape rapidly, but their surroundings rearrange much more slowly, and this lag shows up in the measurements. The study has been published in The Journal of Chemical Physics. 
November 10, 2026
Physicists Train AI to Optimise Particle Beams in Accelerators
Researchers from the AI and Digital Science Institute at the HSE Faculty of Computer Science and the Budker Institute of Nuclear Physics at the Siberian Branch of the Russian Academy of Sciences have developed RLABC (Reinforcement Learning for Accelerator Beamline Control), a framework that uses reinforcement learning to identify optimal settings for a particle accelerator. In a computer simulation, RLABC optimised the accelerator's parameters to achieve a particle transmission rate of 70%. The study has been published in Computer Physics Communications.
November 9, 2026
'Organ-on-a-Chip Technology Could Eliminate the Need for Animal Testing'
The Laboratory of Molecular Physiology at the HSE Faculty of Biology and Biotechnology investigates how molecular regulators known as microRNAs control gene expression and contribute to the development of diseases, including cancer, viral and inflammatory conditions, and pregnancy complications. At HSE University, researchers develop organ-on-a-chip models: miniature devices containing living cells that mimic the functions of human organs, such as the placenta and intestines. These models help researchers understand how diseases develop and how drugs affect them. HSE News Service spoke with Evgeny Knyazev, Head of the Laboratory.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Parallel Heuristic Exploration for Additive Complexity Reduction in Fast Matrix Multiplication

2025.
Perminov Andrew Igorevich
This paper presents a parallel random-search method for reducing additive complexity in fast matrix multiplication algorithms with ternary coefficients {−1,0,1}. The approach replaces expensive exact evaluation with fast heuristic scoring, including the new Greedy-Intersections strategy. The method runs many independent common subexpression elimination processes in parallel, exploring the search space through random pair substitutions and diverse selection strategies while sharing promising partial solutions. Tested on 149 ternary-coefficient schemes, the method achieves lower addition counts than the state-of-the-art Greedy-Potential on 102 schemes (including 57 new best-known results for optimal-rank schemes), matches it on 45, and is outperformed on only 2. For most schemes, it provides equal or better results while being significantly faster, making it practical for algorithm exploration. All software and results are open source.
Language: English
DOI
Text on another site
Keywords: fast matrix multiplicationadditive complexity reductioncommon subexpression eliminationternary coefficient set
Similar publications
Fast Matrix Multiplication via Ternary Meta Flip Graphs
Perminov Andrew Igorevich, / Series Computer Science "arxiv.org". 2025.
Matrix multiplication optimization remains a fundamental challenge in computational mathematics. This work introduces a novel approach that discovers matrix multiplication schemes whose coefficients are restricted to the set {−1,0,1} (denoted ZT), minimizing naive additive complexity for efficient hardware implementation. The core of the method is a GPU-accelerated meta flip graph algorithm that maintains ternary safety ...
Added: September 14, 2026
A 58-Addition, Rank-23 Scheme for General 3 × 3 Matrix Multiplication
Perminov Andrew Igorevich, / Series Computer Science "arxiv.org". 2025.
This paper presents a new state-of-the-art algorithm for exact 3×3 matrix multiplication over general non-commutative rings, achieving a rank-23 scheme with only 58 scalar additions. This improves the previous best additive complexity of 60 additions without a change of basis. The result was discovered through an automated search combining ternary-restricted flip-graph exploration with greedy intersection ...
Added: September 14, 2026
Fast Matrix Multiplication in Small Formats: Discovering New Schemes with an Open-Source Flip Graph Framework
Perminov Andrew Igorevich, / Series Computer Science "arxiv.org". 2026.
An open-source C++ framework for discovering fast matrix multiplication schemes using the flip graph approach is presented. The framework supports multiple coefficient rings -- binary (Z2), modular ternary (Z3) and integer ternary (ZT={−1,0,1}) -- and implements both fixed-dimension and meta-dimensional search operators. Using efficient bit-level encoding of coefficient vectors and OpenMP parallelism, the tools enable ...
Added: September 14, 2026
Meta Flip Graph meets Serendipitous Product: new Fast Matrix Multiplication results
Perminov Andrew Igorevich, / Series Computer Science "arxiv.org". 2026.
This paper presents new results for fast matrix multiplication in small formats obtained by combining the meta flip graph framework with the serendipitous product construction. The framework has been extended to support all 680 rectangular formats with dimensions up to 16×16×16. Compared to the previous state of the art, ranks are improved for 207 formats. ...
Added: September 14, 2026
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit