Rakesearch: Difference between revisions
update and infobox |
No edit summary |
||
| Line 28: | Line 28: | ||
| website = {{URL|https://rake.boincfast.ru/rakesearch/}} | | website = {{URL|https://rake.boincfast.ru/rakesearch/}} | ||
}} | }} | ||
[https://rake.boincfast.ru/rakesearch/ '''''RakeSearch'''''] is a BOINC based '''''[[wikipedia:Volunteer computing|volunteer computing]]''''' project that needs your help to process diagonal Latin squares. | [https://rake.boincfast.ru/rakesearch/ '''''RakeSearch'''''] is a BOINC based '''''[[wikipedia:Volunteer computing|volunteer computing]]''''' project that needs your help to process diagonal Latin squares. | ||
Latest revision as of 13:25, 28 May 2026
RakeSearch is a BOINC based volunteer computing project that needs your help to process diagonal Latin squares.
Background: Latin squares and their diagonals
A Latin square of order <math>n</math> is an <math>n \times n</math> array filled with <math>n</math> different symbols, each occurring exactly once in every row and exactly once in every column.[1] Formally, it is a set of <math>n^2</math> triples <math>(r, c, s)</math> such that all ordered pairs <math>(r, c)</math>, <math>(r, s)</math>, and <math>(c, s)</math> are distinct.
A diagonal Latin square (DLS) of order <math>n</math> is a Latin square in which both the main diagonal and the main antidiagonal also contain each of the <math>n</math> symbols exactly once.[2] This additional constraint makes diagonal Latin squares considerably rarer and more difficult to enumerate than ordinary Latin squares. They are closely related to magic squares and have applications in experimental design and combinatorics.
Two Latin squares <math>A</math> and <math>B</math> of the same order <math>n</math> are said to be orthogonal if, when superimposed, every ordered pair of symbols appears exactly once across the <math>n^2</math> cells. A pair of mutually orthogonal diagonal Latin squares is abbreviated ODLS. It has been proved that ODLS of order <math>n</math> exist for all <math>n</math> except <math>n \in \{2, 3, 6, 10, 14, 15, 18, 26\}</math>, with the first three being provably impossible.[3]
The orthogonality graph of a set of diagonal Latin squares has one node per DLS and an edge between any two squares that are mutually orthogonal. Characterizing these graphs for squares of increasing order is a central goal of RakeSearch.
Why RakeSearch?
The total number of diagonal Latin squares grows super-exponentially with order. The number of reduced DLS of order 9 alone runs into the billions, making brute-force enumeration of all objects impractical on any single machine or even on conventional HPC clusters within a reasonable timeframe.[4] Volunteer distributed computing provides the only viable path to exhaustively probe the structure of the space for orders 9 and above.
Beyond sheer scale, many key quantities — such as the number of transversals, the spectrum of intercalates, and the structure of orthogonality graphs — were either entirely unknown or known only approximately before the project began. Several of these have since been confirmed or newly computed by RakeSearch and submitted to the On-Line Encyclopedia of Integer Sequences (OEIS).[5]
Goal
Investigate the diagonal Latin squares space. Specifically, the project aims to:
- Enumerate and characterize the orthogonality graphs of diagonal Latin squares of orders 9, 10, and beyond.
- Determine exact values for numerical characteristics of DLS such as the number of transversals, diagonal transversals, and intercalates.
- Confirm, extend, or newly establish integer sequences in the OEIS related to DLS.
- Support joint experiments with the related Gerasim@home project on the BOINC platform.
Methods
[4] The enormous size of the diagonal Latin squares space makes it unfeasible to enumerate all its objects in reasonable time. Sophisticated search methods and the BOINC platform are essential to meet the computational requirements.
RakeSearch implements an application that picks up separate pairs of mutually orthogonal DLS, which allows reconstruction of full graphs of their orthogonality.
The core strategy is a rake search: starting from a single DLS, the application systematically searches for all squares that are row-permutational ODLS partners to it, building up the local neighborhood in the orthogonality graph. A work unit corresponds to one such search rooted at a particular base square. The full set of work units covers the entire space at the current order.
For order 9, the complete space comprised approximately 23.3 million work units. As of January 2018, after roughly five months of operation, over 1.2 million units had been processed.[6]
A community-developed optimized application, maintained separately on GitHub, provides substantially faster runtimes on both x86 and x86_64 hardware using SSE2 and SSSE3 instruction sets.[7]
Active applications
As of May 2026, the project runs four application streams:[8]
- Joint search of ODLS12 with Gerasim project — searching for orthogonal pairs of diagonal Latin squares of order 12 in collaboration with the Gerasim@home project.
- Joint search of DLS spectra with Gerasim project — computing spectra of numerical characteristics in collaboration.
- Generalized symmetries in parastrophic slices for DLS of order 10 — studying structural symmetries in the order-10 space.
- Spectra of Latin squares — constructing spectra of numerical characteristics (transversals, intercalates, etc.) for Latin squares of higher orders.
Source code
History
RakeSearch was launched on 8 September 2017, initially as a Linux-only CPU project hosted on the BOINC infrastructure operated by the boincfast.ru community.[9] Windows application support was added in the months following launch. The project was presented at the BOINC:FAST 2017 conference, where two presentations on ODLS generated by row permutation were given.[5]
In its first phase, the project focused on exhaustive characterization of the DLS space of order 9 (R9). The R9 search was formally completed and archived, with all results, workunits, graphs, and source code published.[4]
The project subsequently moved to order 10 (R10), and later to higher-order experiments including searches for spectra of transversals and intercalates for orders up to 25 and beyond. Following a period of inactivity and a hardware failure (loss of both mirror SSD discs), the project was relaunched with new hardware and updated BOINC server software.[10]
The project is a collaboration with Gerasim@home, also operated by Eduard Vatutin and colleagues, which handles related enumeration tasks on the BOINC platform at gerasim.boinc.ru.
Project team / Sponsors
The project is developed and maintained by Natalia Nikitina (Institute of Applied Mathematical Research, Karelian Research Center of the Russian Academy of Sciences, Petrozavodsk) and the volunteer known as hoarfrost, with the broader The searchers team at the Karelian Research Center of the Russian Academy of Sciences.[11]
Scientific co-authors on published results include Eduard Vatutin (Southwest State University, Kursk), Maxim Manzyuk (Internet portal BOINC.RU, Moscow), Oleg Zaikin, Stepan Kochemazov, Alexey Belyshev, Alexander Albertian, Ilya Kurochkin, Alexander Kripachev, Alexey Pykhtin, Ilya Chernov, and Evgeny Ivashko, among others.[5]
The project received financial support from the Russian Foundation for Basic Research under grant numbers 18-07-00628_a, 18-37-00094_mol_a, and 17-07-00317_a.[11]
Scientific results
RakeSearch has produced a range of verified mathematical results since its launch. Completed search archives and the discovered orthogonality graphs are published on the project graphs page.[4]
OEIS sequences confirmed, updated, or newly discovered
The following sequences in the On-Line Encyclopedia of Integer Sequences (OEIS) have been confirmed, updated (values corrected), rechecked (independently re-derived), or newly established based on RakeSearch experiments:[5]
| Sequence | Description | Status |
|---|---|---|
| A287644 | Maximal number of transversals in a diagonal Latin square of order <math>n</math> | Confirmed |
| A287645 | Minimal number of transversals in a diagonal Latin square of order <math>n</math> | Confirmed |
| A287647 | Minimal number of diagonal transversals in a diagonal Latin square of order <math>n</math> | Confirmed |
| A287648 | Maximal number of diagonal transversals in a diagonal Latin square of order <math>n</math> | Confirmed |
| A287651 | Number of reduced pairs of orthogonal diagonal Latin squares of order <math>n</math> | Updated |
| A287695 | Maximal number of normalized DLS that can be orthogonal to the same DLS of order <math>n</math> | Confirmed |
| A287764 | Number of main classes of diagonal Latin squares of order <math>n</math> | Rechecked |
| A307163 | Minimal number of intercalates in a diagonal Latin square of order <math>n</math> | Confirmed |
| A307164 | Maximal number of intercalates in a diagonal Latin square of order <math>n</math> | Confirmed |
| A309210 | Number of main classes of extended self-orthogonal DLS of order <math>n</math> | Updated |
| A329685 | Number of main classes of self-orthogonal DLS of order <math>n</math> | Confirmed |
| A330391 | Number of main classes of DLS of order <math>n</math> with at least one orthogonal diagonal mate | Updated |
| A333366 | Number of main classes of doubly self-orthogonal DLS of order <math>n</math> | Confirmed |
| A338250 | Number of isomorphism classes of pairs of orthogonal DLS of order <math>n</math> | New |
| A339926 | Number of pairs of orthogonal DLS of order <math>n</math> | New |
SAT-based search
RakeSearch has also hosted a SAT-CMS-based (cube-and-conquer) experiment to search for orthogonal diagonal Latin squares of order 10, with found pairs published on the project site.[4] This method was described formally in a 2021 paper.[12]
Scientific publications
The following is a list of conference papers with results arising from RakeSearch. Source: BOINC Publications list and the project publications page.
Conference papers
- "Diagonalization and Canonization of Latin Squares". In:(2023}).Supercomputing. RuSCDays 2023. Springer. DOI: 10.1007/978-3-031-49435-2_4.
- "Searching for Orthogonal Latin Squares via Cells Mapping and BOINC-Based Cube-and-Conquer". In:(2021}).Supercomputing. RuSCDays 2021. Springer. DOI: 10.1007/978-3-030-92864-3_38.
- "Enumerating the Orthogonal Diagonal Latin Squares of Small Order for Different Types of Orthogonality". In:(2020}).Supercomputing. RuSCDays 2020. Springer. DOI: 10.1007/978-3-030-64616-5_50.
- "Replication of "Tail" Computations in a Desktop Grid Project". In:(2020}).Supercomputing. RuSCDays 2020. Springer. DOI: 10.1007/978-3-030-64616-5_52.
- Vatutin, Eduard.(2020})."Second International Conference Information, Computation, and Control Systems for Distributed Environments 2020 (ICCS-DE 2020)".link.
- "Start-up and the Results of the Volunteer Computing Project RakeSearch". In:(2019}).Supercomputing. RuSCDays 2019. Springer. pp. 725–734. DOI: 10.1007/978-3-030-36592-9_59.(Communications in Computer and Information Science, vol. 1129).
- "On Sharing Workload in Desktop Grids". In:(2018}).Supercomputing. RuSCDays 2018. Springer. DOI: 10.1007/978-3-030-05807-4_51. (uses statistics from RakeSearch)
Papers in press / recent
- Vatutin, E. et al. Simulation of Volunteer Computing in a Desktop Grid System, Russian Supercomputing Days 2024. DOI: 10.1007/978-3-031-78462-0_9 (uses statistics from RakeSearch)
- Vatutin, E. et al. Construction of heuristic approximations of the spectra of the number of intercalates in diagonal Latin squares of orders 10-25, National Supercomputing Forum 2024 (NSCF-2024). (in press)
- Vatutin, E. et al. Construction of the spectra of intercalates number in the Latin squares of orders 18-28 using volunteer distributed computing in the BOINC platform, Recognition 2025. (in press)
- Vatutin, E. et al. Using spectra of numerical characteristics of Latin squares during getting spectra of diagonal Latin squares, Science and Education in the Development of Industrial, Social and Economic Spheres of Russian Regions. Murom, 2025. (in press)
Presentations
- Modification of the load balancing method in a desktop grid for solving problems of constructing Latin square spectra, GRID'2025, 2025.
- Start-up and the results of the volunteer computing project RakeSearch, Russian Supercomputing Days 2019.
- Petrozavodsk Desktop Grid Community, BOINC Workshop 2018.
- Characterizing orthogonal diagonal Latin squares of order 9 discovered in a distributed computing project, Recognition-2018.
- ODLS generated by rows permutation, BOINC:FAST 2017.
Server status
As of 23 May 2026, the project server reports the following statistics:[13]
| Metric | Value |
|---|---|
| Current GigaFLOPS | 12,351.63 |
| Users with credit | 2,528 |
| Users with recent credit | 522 |
| Computers with credit | 13,104 |
| Computers with recent credit | 1,661 |
| Tasks ready to send | 15,463 |
| Tasks in progress | 16,012 |
Research progress on current enumeration targets (percentage of space explored):
| Target | Progress (%) |
|---|---|
| E0043 | 6.315 |
| E1056 | 1.391 |
| E1067 | 5.670 |
| E1076 | 0.065 |
| E1079 | 2.037 |
Contributing
To participate, download and install the BOINC client and attach to the project at https://rake.boincfast.ru/rakesearch/. The project currently supports Windows (x86_64) and Linux platforms, with CPU-only computation. Account creation requires either registration through the project website (an invitation code from Crunch_4Science is needed for web registration) or direct attachment via the BOINC Manager.
See also
References
- ↑ Latin square. Wikipedia. Retrieved 2026-05-23}}.
- ↑ A274171. OEIS. Retrieved 2026-05-23}.
- ↑ Orthogonal diagonal latin squares of order 14. Journal of the Australian Mathematical Society. DOI: 10.1017/S1446788700011782. Retrieved 2026-05-23}.
- ↑ 4.0 4.1 4.2 4.3 4.4 About RakeSearch project. RakeSearch. Retrieved 2026-05-23}.
- ↑ 5.0 5.1 5.2 5.3 Publications on RakeSearch project. RakeSearch. Retrieved 2026-05-23}.
- ↑ RakeSearch project technical update 2018-01-06. The Scottish Boinc Team. Retrieved 2026-05-23}.
- ↑ RakeSearch (GitHub, sirzooro). GitHub. Retrieved 2026-05-23}.
- ↑ RakeSearch server status. RakeSearch. Retrieved 2026-05-23}.
- ↑ RakeSearch. [H]ard. Retrieved 2026-05-23}.
- ↑ RakeSearch — new experiment. The Scottish Boinc Team. Retrieved 2026-05-23}.
- ↑ 11.0 11.1 "Start-up and the Results of the Volunteer Computing Project RakeSearch". In:(2019}).Supercomputing. RuSCDays 2019. Springer. pp. 725–734. DOI: 10.1007/978-3-030-36592-9_59.(Communications in Computer and Information Science, vol. 1129).
- ↑ "Searching for Orthogonal Latin Squares via Cells Mapping and BOINC-Based Cube-and-Conquer". In:(2021}).Supercomputing. RuSCDays 2021. Springer. DOI: 10.1007/978-3-030-92864-3_38.
- ↑ (2026-05-23}).RakeSearch server status. RakeSearch. Retrieved 2026-05-23}.