Rakesearch

From BOINC Projects
Jump to navigation Jump to search



RakeSearch
Project
StatusActive
CategoryMathematics
ComputeCPU
Development
DeveloperNatalia Nikitina, hoarfrost
AuthorNatalia Nikitina
SponsorKarelian Research Center of the Russian Academy of Sciences
MaintainerThe searchers team, Karelian Research Center of the Russian Academy of Sciences
Initial releaseSeptember 7, 2017  (9 years ago)
RepositoryGitHub (community-optimized client)
Software
Written inC++
Operating systemWindows, Linux
BOINC statistics
Stats as ofMay 23, 2026  (0 years ago)
Performance12,351 GigaFLOPS
Active users522
Total users2,528
Active hosts1,661
Total hosts13,104
Metadata
Websitehttps://rake.boincfast.ru/rakesearch/

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 n is an n×n array filled with n different symbols, each occurring exactly once in every row and exactly once in every column.[1] Formally, it is a set of n2 triples (r,c,s) such that all ordered pairs (r,c), (r,s), and (c,s) are distinct.

A diagonal Latin square (DLS) of order n is a Latin square in which both the main diagonal and the main antidiagonal also contain each of the n 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 A and B of the same order n are said to be orthogonal if, when superimposed, every ordered pair of symbols appears exactly once across the n2 cells. A pair of mutually orthogonal diagonal Latin squares is abbreviated ODLS. It has been proved that ODLS of order n exist for all n except n∈{2,3,6,10,14,15,18,26}, 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

Penyelesaian Sudoku

[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

The BOINC platform, on which RakeSearch runs.
The BOINC platform, on which RakeSearch runs.

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 n Confirmed
A287645 Minimal number of transversals in a diagonal Latin square of order n Confirmed
A287647 Minimal number of diagonal transversals in a diagonal Latin square of order n Confirmed
A287648 Maximal number of diagonal transversals in a diagonal Latin square of order n Confirmed
A287651 Number of reduced pairs of orthogonal diagonal Latin squares of order n Updated
A287695 Maximal number of normalized DLS that can be orthogonal to the same DLS of order n Confirmed
A287764 Number of main classes of diagonal Latin squares of order n Rechecked
A307163 Minimal number of intercalates in a diagonal Latin square of order n Confirmed
A307164 Maximal number of intercalates in a diagonal Latin square of order n Confirmed
A309210 Number of main classes of extended self-orthogonal DLS of order n Updated
A329685 Number of main classes of self-orthogonal DLS of order n Confirmed
A330391 Number of main classes of DLS of order n with at least one orthogonal diagonal mate Updated
A333366 Number of main classes of doubly self-orthogonal DLS of order n Confirmed
A338250 Number of isomorphism classes of pairs of orthogonal DLS of order n New
A339926 Number of pairs of orthogonal DLS of order n 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. Sources: BOINC publications list and the project publications page. Papers whose computations ran in both RakeSearch and Gerasim@home are listed on both project pages, with a note saying where the experiments were performed. Entries are ordered newest first; titles link to the publisher's version or to a full-text copy.

Conference papers

  1. Vatutin, E. I., et al. (2025). Construction of the spectra of intercalates number in the Latin squares of orders 18–28 using volunteer distributed computing in the BOINC platform. Optoelectronic Equipment and Devices in Systems of Pattern Recognition, Image and Symbol Information Processing (Recognition-2025), Kursk, pp. 33–34.
  2. Petrenko, Ksenia; Ilya Kurochkin (2025). Simulation of Volunteer Computing in a Desktop Grid System. Supercomputing (RuSCDays 2024), Lecture Notes in Computer Science 15407:120–134. DOI: 10.1007/978-3-031-78462-0_9. (uses statistics gathered in RakeSearch)
  3. Vatutin, E. I.; N. N. Nikitina; M. O. Manzyuk; I. I. Kurochkin; A. M. Albertyan (2024). On the number of transversals in diagonal Latin squares of even orders. Cloud and Distributed Computing Systems (ORVS-2023), National Supercomputing Forum (NSCF-2023), Pereslavl-Zalessky, pp. 101–105. (in Russian; shared with Gerasim@home — order-9 experiments run in both projects on BOINC)
  4. Vatutin, Eduard; Alexey Belyshev; Natalia Nikitina; Maxim Manzuk; Alexander Albertian; Ilya Kurochkin; Alexander Kripachev; Alexey Pykhtin (2023). Diagonalization and Canonization of Latin Squares. Supercomputing (RuSCDays 2023), Lecture Notes in Computer Science 14389:48–61. DOI: 10.1007/978-3-031-49435-2_4. (shared with Gerasim@home — both projects named in the keywords and credited for the calculations)
  5. Vatutin, E. I. (2023). Strategy of distributed diagonalization of Latin squares. Science and Education in the Development of Industrial, Social and Economic Spheres of Russian Regions, Murom, pp. 118–120. (in Russian; about 10,000 workunits computed in RakeSearch)
  6. Vatutin, E. I.; N. N. Nikitina; M. O. Manzyuk; I. I. Kurochkin; A. M. Albertyan; A. V. Kripachev; A. I. Pykhtin (2023). Methods for constructing spectra of rapidly computable numerical characteristics of diagonal Latin squares. Cloud and Distributed Computing Systems in Electronic Management (ORVSEU-2022), National Supercomputing Forum (NSCF-2022), Pereslavl-Zalessky, pp. 19–23. (in Russian; shared with Gerasim@home — order-13 spectrum computed in RakeSearch)
  7. Vatutin, E. I.; V. S. Titov; A. I. Pykhtin; A. V. Kripachev; N. N. Nikitina; M. O. Manzyuk; A. M. Albertyan; I. I. Kurochkin (2022). Estimation of the cardinalities of spectra of rapidly computable numerical characteristics of diagonal Latin squares of orders N>9. Science and Education in the Development of Industrial, Social and Economic Spheres of Russian Regions, Murom, pp. 118–119. (in Russian; listed by the RakeSearch project, but the paper credits the computations to Gerasim@home only)
  8. Vatutin, Eduard; Oleg Zaikin; Maxim Manzyuk; Natalia Nikitina (2021). Searching for Orthogonal Latin Squares via Cells Mapping and BOINC-Based Cube-and-Conquer. Supercomputing (RuSCDays 2021), Communications in Computer and Information Science 1510:498–512. DOI: 10.1007/978-3-030-92864-3_38. (shared with Gerasim@home — Cube-and-Conquer stage run in RakeSearch, ESODLS CMS search in Gerasim@Home; both sets of volunteers thanked)
  9. Vatutin, Eduard; Alexey Belyshev (2020). Enumerating the Orthogonal Diagonal Latin Squares of Small Order for Different Types of Orthogonality. Supercomputing (RuSCDays 2020), Communications in Computer and Information Science 1331:586–597. DOI: 10.1007/978-3-030-64616-5_50. (shared with Gerasim@home — enumeration run in Gerasim@Home, using row-permutation ODLS pairs found in RakeSearch)
  10. Ivashko, Evgeny; Natalia Nikitina (2020). Replication of "Tail" Computations in a Desktop Grid Project. Supercomputing (RuSCDays 2020), Communications in Computer and Information Science 1331:611–621. DOI: 10.1007/978-3-030-64616-5_52. (uses statistics gathered in RakeSearch)
  11. Vatutin, Eduard; Natalia Nikitina; Alexey Belyshev; Maxim Manzyuk (2020). On polynomial reduction of problems based on diagonal Latin squares to the exact cover problem. Information, Computation, and Control Systems for Distributed Environments (ICCS-DE 2020), CEUR Workshop Proceedings 2638:289–297. (listed by the RakeSearch project; computational experiments performed in Gerasim@home on BOINC)
  12. Manzyuk, Maxim; Natalia Nikitina; Eduard Vatutin (2019). Start-up and the Results of the Volunteer Computing Project RakeSearch. Supercomputing (RuSCDays 2019), Communications in Computer and Information Science 1129:725–734. DOI: 10.1007/978-3-030-36592-9_59.
  13. Chernov, Ilya (2019). On Sharing Workload in Desktop Grids. Supercomputing (RuSCDays 2018), Communications in Computer and Information Science 965:599–608. DOI: 10.1007/978-3-030-05807-4_51. (uses statistics from RakeSearch)

Papers in press / recent

Both are cited as published in the Recognition-2025 paper above.

  1. Vatutin, Eduard; Jia Wei-Ting; Jun Chi Ma; Qiang Miao (2025). Construction of heuristic approximations of the spectra of the number of intercalates in diagonal Latin squares of orders 10–25. National Supercomputing Forum (NSCF-2024), pp. 8–12.
  2. Vatutin, Eduard; Jia Wei-Ting; Jun Chi Ma; Qiang Miao (2025). 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, pp. 228–231.

Presentations

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 or direct attachment via the BOINC Manager.

See also

References

  1. ↑ Latin square. Wikipedia. Retrieved 2026-05-23.
  2. ↑ A274171. OEIS. Retrieved 2026-05-23.
  3. ↑ Orthogonal diagonal latin squares of order 14. Journal of the Australian Mathematical Society. DOI: 10.1017/S1446788700011782. Retrieved 2026-05-23.
  4. ↑ 4.0 4.1 4.2 4.3 4.4 About RakeSearch project. RakeSearch. Retrieved 2026-05-23.
  5. ↑ 5.0 5.1 5.2 5.3 Publications on RakeSearch project. RakeSearch. Retrieved 2026-05-23.
  6. ↑ RakeSearch project technical update 2018-01-06. The Scottish Boinc Team. Retrieved 2026-05-23.
  7. ↑ RakeSearch (GitHub, sirzooro). GitHub. Retrieved 2026-05-23.
  8. ↑ RakeSearch server status. RakeSearch. Retrieved 2026-05-23.
  9. ↑ RakeSearch. [H]ard. Retrieved 2026-05-23.
  10. ↑ RakeSearch — new experiment. The Scottish Boinc Team. Retrieved 2026-05-23.
  11. ↑ 11.0 11.1 "Start-up and the Results of the Volunteer Computing Project RakeSearch". In:Manzyuk, Maxim; Nikitina, Natalia; Vatutin, Eduard.(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).
  12. ↑ "Searching for Orthogonal Latin Squares via Cells Mapping and BOINC-Based Cube-and-Conquer". In:Vatutin, Eduard; Zaikin, Oleg; Manzyuk, Maxim; Nikitina, Natalia.(2021).Supercomputing. RuSCDays 2021. Springer. DOI: 10.1007/978-3-030-92864-3_38.
  13. ↑ (2026-05-23).RakeSearch server status. RakeSearch. Retrieved 2026-05-23.

External links

Retrieved from "https://boincsynergy.ca/wiki/index.php?title=Rakesearch&oldid=1976"