Exact Enumeration of Solid Partitions

This is the home page for the project set up for counting solid partitions. The goal of the project is to count the number of solid partitions of all positive integers $\leq 100.$ At the start of this project in September 2010, the numbers are known for positive integers $\leq 50.$ The tentative schedule for this project are as follows:

Year	2010	2011	2012	2013	2014	2015
N	52	60	70	80	90	100
Est $\mathbf{p_3(N)}$	$10^{14}$	$10^{16}$	$10^{18}$	$10^{20}$	$10^{22}$	$10^{24}$

As one can see, each step involves a hundredfold increase in requirements. This can be achieved in several ways: improvements in the code, increasing the number of branches, new ideas in parallelization, faster computers etc. Will we be able to achieve the above schedule? Only time will provide the answer to this question.

Results

Date	Oct. 2010	Nov. 2010	Dec. 2010	June 2011
N	52	55	62	68
Code used	v2.0	v3.0	v3.2	v3.2
Branches	1491	1542	4167	18334

Current state of the project: Paused (new ideas needed) To be restarted soon!

We have a working program written in C++ that can reproduce some of the known numbers in reasonable time.

• [Sept 12, 2010] The code has been parallelized with 1491 branches and tested to reproduce known results for N=40 (with the help of Naveen Sharma).
• [Sept 13, 2010] Starting running the long branches (for N=52) on the Leo supercluster at IITM. Began the process for setting up the interface for volunteer computing. Arun Chaganty suggests that we run code with O3 optimization and it is seen to provide a factor of three improvement in run times. So we expect the longest branches to run in less than 5 days (on Leo) instead of the initial estimate of 10 days.
• [Sept 14, 2010] Have a shell script that validates submissions of results.
• [Sept 21-22, 2010] Runs A and B on all three trunks(=451/1491 branches) completed. Used leo/vega/physics/curie to run all the jobs. Eventually jobs were bunched together (‘undoing’ some of the parallelization) so that run times for each bunch were of the order of 5 days. Awaiting the setting up the portal for volunteer computing so that the remaining runs are carried out by volunteers.
• [Oct 16, 2010] All the N=52 runs have been completed. Need to combine them to get the number of solid partitions. Benchmarking for the N=60 runs being carried out. It appears that run times (for N=60) increase by a factor of 360 with respect to the N=52 run times.
• [Oct 17, 2010] Completed the N=52 run and we now have two new numbers of solid partitions. Here are the results for N<=52.

(1)

\begin{align} \boxed{ p_{3}(51) = 11622\ 14153\ 25837\quad \textrm{and}\quad p_3(52) = 19379\ 44766\ 58112 \nonumber } \end{align}

• [Oct 20, 2010] Breakthrough in parallelization: Srivatsan proposes working with an equivalence classes of branches — all branches that belong to an equivalence class have the same subsequent tree. This implies that one run per equivalence class will suffice provided one tracks the multiplicities of equivalence classes. Thanks to this observation, we can now we can go to higher depths. For instance, at depth 12, there are around 28 million branches but only 5172 equivalence classes. This will be incorporated in the next run for N=60 or larger number.
• [Oct 24, 2010] v3.0 of code has been parallelized at depth 10 with 1542 branches. Testing with N=55. This is a prelude to running the code for N=60 using volunteer computing.
• [Oct 28, 2010] Srivatsan creates v3.2 of the code. The modification (w.r.t v3.0) is that the dependence on the end-point is removed in the equivalence class. While this is a minor improvement, it is significant as it reduces the the number of equivalence class by a factor of 4 at depth 12 (5172 becomes 1479). It is clear that we can compute the number of solid partitions $\leq 70$ but going beyond this will need a significant improvement.
• [Nov 3, 2010] v3.0 of the code at depth 10 provides three new numbers. Here are the complete results for N<=55.

(2)

\begin{align} \boxed{ p_3(53) = 32238\ 23655\ 07746\ ,\ p_3(54) = 53505\ 67710\ 14674\ , \ p_3(55) = 88603\ 33844\ 75166 \nonumber } \end{align}

• [Nov 7, 2010] Proved that the number of equivalence classes at a depth $k$ is the same as the number of plane partitions of $k$. This provides a simple formula for the number of equivalence classes at any depth.
• [Nov 10, 2010] Started the run for N=62 using a parallelized version of the v3.2 at depth 14 (=4167 equivalence classes). Results are expect at the end of December/early January. The code has been tested to reproduce results for N=50. Some of the parts will be done through volunteer computing — the portal is expected to be ready soon.
• [Dec 1, 2010] Issues with the parallel file system on the supercluster Vega led to its closure for a week. Then, it came back up but errors persisted with some data files not getting written. Things are back on track now and results should be expected by Dec. 10 or latest by Dec. 15. Portal isn't ready yet.
• [Dec 7, 2010] Testing for N=70 at depth 16 already started with validation of the branching with a N=55 run. No improvements in code since the previous run. Hopefully, it will arrive soon enough! Outlook for obtaining numbers beyond 70 remain bleak unless we come up with improvements.
• [Dec 9, 2010] All the runs for N=62 have been completed. Here are the complete results for N<=62. Here are the seven new numbers that we have added bringing the total number of additions to twelve.

(3)

\begin{align} \boxed{ p_3(56) = 1 46400 93392 99229\ ,\ p_3(57) = 2 41380 42828 01444\ ,\ p_3(58) = 3 97140 96826 33930\ ,\ p_3(59) = 6 52064 95439 12193\ ,\ } \end{align}

(4)

\begin{align} \boxed{ p_3(60) = 10 68461 42257 15559\ ,\ p_3(61) = 17 47294 70062 57293\ ,\ p_3(62) = 28 51869 10933 88854\ .\ } \end{align}

• [Dec 14, 2010] Successfully completed the test run for N=55 at depth 16 using v3.2 of code. Carrying out timing runs for N=70 at the same depth. Naive scaling suggests that some branches will need runs of greater than 10 days. May need to go to higher depth and/or use an openmpi version of the program for the longer runs. Going beyond N=70 remains bleak.
• [Dec 29, 2010] Generated the 18334 branches for depth 17 — took more than 200 hours of CPU time. Need to start a timing run (as well as branching test) for N=55 before starting the code for N=70. Expect results for N=70 towards the end of February 2011. Naveen has a working version of the Monte Carlo code for 1D partitions.
• [Jan 3, 2011] N=55 test run at depth 17 has been completed and the branching has been validated. 5000 of the 18334 branches for N=70 have been submitted to the HPCE machine and runs will be done during the last week of January.
• [Jan 21, 2011] It appears more practical to aim to get the number of solid partitions for N=68 in the current run. The timings of the ongoing run involving the branches with smaller runtimes leads us to this conclusion. So the remaining 13334 branches will be run for N=68. This way the results will be available during April 2011. Future runs will be undertaken after we come up with modifications that might enable us to go beyond N=68.
• [Feb 22, 2011] Around 10,500 branches have been submitted to Leo/Vega. Of these, 6000+ branches have been completed and the remaining will get done towards the end of March. The remaining 8000+ branches will be start running in the second half of March and will hopefully be done by the end of April.
• [March 27, 2011] Was travelling for 3 weeks and our supercluster vega was rebooted during that period. Lost about 2-3 weeks of runtime as I have no remote access to vega. Restarted all jobs only early last week. We should now expect to be done only in May. 10,000+ branches have been completed. Another 2,000 branches have been submitted.
• [April 19, 2011] Yet another stoppage on vega — the vendor has promised to fix the SFS problem for good. Only a handful of jobs are running on the smaller cluster leo for now. About 12500 branches have been completed. Hopefully, the numbers will be out by the end of May. Meanwhile, here are the new set of predictions.
• [May 19, 2011] About 96% of the jobs are done. 814 branches are to be completed hopefully by the end of this month. The SFS problem in vega appears to have been fixed this time around and things have been going smoothly. A manuscript on the asymptotics of higher dimensional partitions with Srivatsan and Naveen as co-authors is being readied for publication.
• [June 1, 2011] Runs are completed. Validation of data is going on and results will be available in a day or two. The paper with Naveen and Srivatsan has appeared on the arXiv without the N=68 data. That will be included once the results are ready. Here is a figure which shows how well the asymptotic formula works.

• [June 1, 2011] Here are six new numbers.

(5)

\begin{align} \boxed{ p_3(63)= 46458506464748807 \ , \ p_3(64)= 75542021868032878\ , \ p_3(65)= 122606799866017598\ , \ } \end{align}

(6)

\begin{align} \boxed{ p_3(66)=198635761249922839 \ , \ p_3(67)=321241075686259326 \ , \ p_3(68)= 518619444932991189 \ . \ } \end{align}

• [June 4, 2011] The solid partitions project will be taking a break. The next run will be carried out once we have fresh ideas that lead to further improvement in the code. Meanwhile, the focus will shift to enumerating four and five dimensional partitions by porting v3.2 of the code. The home pages for these projects are: Four Dimensional Partitions || Five Dimensional Partitions.
• [Feb 2, 2012] Intel India expresses interest in this project and is going to support this project by providing financial support and more importantly will also provide access to computing power as well as technical support. The next run for N=74 is being planned.

Programming aspects

People who have shown interest in this project:

• B. Srivatsan (who has written the first working program and improved on it)
• Suresh Govindarajan (project coordinator/chief tester)
• Arun Chaganty (is setting up the portal)

Things to do:

• Need to modify approach to go past 68
• Change how data is stored — right now there is an array of size $2^N$ use to store at most $N$ non-zero entries. It makes sense to just store those locations (in the array) which have non-zero entries.
• Create mpi version of the code that automatically generates the sub-tree to some additional depth and creates parallel runs that are automatically given to the nodes for further processing.

.

Immediate Goals:

1. Reproduce numbers of solid partitions $\leq 52$ by the end of —September October 2010.— Done!
2. Set up a portal for distributing the computation over several computers by several users by December 2010. This is occasionally called volunteer computing. Eventually, we will set up a BOINC server. postponed for future runs.
3. Start the next run ($N\ge 60$) by December 2010. Done!
4. Started the next run ($N\sim 70$) ($N\leq 68$) during January 2011.

---

Page maintained by Suresh Govindarajan