Spectrally optimized pointset configurations. (English) Zbl 1375.52021
Summary: The search for optimal configurations of pointsets, the most notable examples being the problems of Kepler and Thompson, have an extremely rich history with diverse applications in physics, chemistry, communication theory, and scientific computing. In this paper, we introduce and study a new optimality criteria for pointset configurations. Namely, we consider a certain weighted graph associated with a pointset configuration and seek configurations that minimize certain spectral properties of the adjacency matrix or graph Laplacian defined on this graph, subject to geometric constraints on the pointset configuration. This problem can be motivated by solar cell design and swarming models, and we consider several spectral functions with interesting interpretations such as spectral radius, algebraic connectivity, effective resistance, and condition number. We prove that the regular simplex extremizes several spectral invariants on the sphere. We also consider pointset configurations on flat tori via (i) the analogous problem on lattices and (ii) through a variety of computational experiments. For many of the objectives considered (but not all), the triangular lattice is extremal.
MSC:
| 52C35 | Arrangements of points, flats, hyperplanes (aspects of discrete geometry) |
| 52A40 | Inequalities and extremum problems involving convexity in convex geometry |
| 35P05 | General topics in linear spectral theory for PDEs |
| 05B05 | Combinatorial aspects of block designs |
| 05B40 | Combinatorial aspects of packing and covering |
Keywords:
eigenvalue optimization; density of states; potential energy minimization; universal optimality; regular polytopes; triangular latticeReferences:
| [1] | Arenas, A., Díaz-Guilera, A., Kurths, J., Moreno, Y., Zhou, C.: Synchronization in complex networks. Phys. Rep. 469(3), 93-153 (2008). doi:10.1016/j.physrep.2008.09.002 · doi:10.1016/j.physrep.2008.09.002 |
| [2] | Baernstein II, A.: A minimum problem for heat kernels of flat tori. Contemp. Math. 201, 227-243 (1997). doi:10.1090/conm/201/02604 · Zbl 0887.58051 · doi:10.1090/conm/201/02604 |
| [3] | Ballinger, B., Blekherman, G., Cohn, H., Giansiracusa, N., Kelly, E., Schürmann, A.: Experimental study of energy-minimizing point configurations on spheres. Exp. Math. 18(3), 257-283 (2009). doi:10.1080/10586458.2009.10129052 · Zbl 1185.68771 · doi:10.1080/10586458.2009.10129052 |
| [4] | Belkin, M., Niyogi, P.: Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15(6), 1373-1396 (2003). doi:10.1162/089976603321780317 · Zbl 1085.68119 · doi:10.1162/089976603321780317 |
| [5] | Belkin, M., Niyogi, P., Sindhwani, V.: Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res. 7, 2399-2434 (2006) · Zbl 1222.68144 |
| [6] | Berger, M.: Sur les premiéres valeurs propres des variétés Riemanniennes. Compos. Math. 26(2), 129-149 (1973) · Zbl 0257.53048 |
| [7] | Bétermin, L.: 2d theta functions and crystallization among Bravais lattices (2015). ArXiv: 1502.03839 · Zbl 1356.82008 |
| [8] | Bétermin, L., Zhang, P.: Minimization of energy per particle among Bravais lattices in \[{R}^2\] R2: Lennard-Jones and thomas-fermi cases. Commun. Contemp. Math. 17(6), 1450,049 (2015). doi:10.1142/S0219199714500497 · Zbl 1329.82019 · doi:10.1142/S0219199714500497 |
| [9] | Biyikoglu, T., Leydold, J., Stadler, P.F.: Laplacian Eigenvectors of Graphs. Springer, Berlin (2007). doi:10.1007/978-3-540-73510-6 · Zbl 1129.05001 · doi:10.1007/978-3-540-73510-6 |
| [10] | Björner, A., Lovász, L., Shor, P.W.: Chip-firing games on graphs. Eur. J. Comb. 12(4), 283-291 (1991). doi:10.1016/s0195-6698(13)80111-4 · Zbl 0729.05048 · doi:10.1016/s0195-6698(13)80111-4 |
| [11] | Borodachov, S.V., Hardin, D.P., Saff, E.B.: Low complexity methods for discretizing manifolds via Riesz energy minimization. Found. Comput. Math. 14(6), 1173-1208 (2014). doi:10.1007/s10208-014-9202-3 · Zbl 1304.31006 · doi:10.1007/s10208-014-9202-3 |
| [12] | Borwein, J.M., Lewis, A.S.: Convex Analysis and Nonlinear Optimization. Springer, Berlin (2006). doi:10.1007/978-0-387-31256-9 · Zbl 1116.90001 · doi:10.1007/978-0-387-31256-9 |
| [13] | Boumal, N., Singer, A., Absil, P.A., Blondel, V.D.: Cramér-Rao bounds for synchronization of rotations. Inf. Inference 3(1), 1-39 (2013). doi:10.1093/imaiai/iat006 · Zbl 1308.94041 · doi:10.1093/imaiai/iat006 |
| [14] | Boyd, S., Diaconis, P., Xiao, L.: Fastest mixing Markov chain on a graph. SIAM Rev. 46(4), 667-689 (2004). doi:10.1137/s0036144503423264 · Zbl 1063.60102 · doi:10.1137/s0036144503423264 |
| [15] | Cassels, J.W.S.: On a problem of Rankin about the Epstein zeta function. Proc. Glasg. Math. Assoc. 4, 73-80 (1959). doi:10.1017/s2040618500033906 · Zbl 0103.27602 · doi:10.1017/s2040618500033906 |
| [16] | Chung, F.R.K.: Spectral Graph Theory. AMS, Providence (1997). doi:10.1090/cbms/092 · Zbl 0867.05046 · doi:10.1090/cbms/092 |
| [17] | Cohen-Tannoudji, C., Dupont-Roc, J., Grynberg, G.: Atom-Photon Interactions. Wiley-Interscience, New York (1992). doi:10.1002/9783527617197 · doi:10.1002/9783527617197 |
| [18] | Cohn, H.: Order and disorder in energy minimization. In: Proceedings of the International Congress of Mathematicians, Hyderabad, India (2010). doi:10.1142/9789814324359_0152 · Zbl 1236.05058 |
| [19] | Cohn, H., Kumar, A.: Universally optimal distribution of points on spheres. J. Am. Math. Soc. 20(1), 99-148 (2007). doi:10.1090/S0894-0347-06-00546-7 · Zbl 1198.52009 · doi:10.1090/S0894-0347-06-00546-7 |
| [20] | Conway, J., Sloane, N.J.A.: Sphere Packings, Lattices and Groups, 3rd edn. Springer, Berlin (1999). doi:10.1007/978-1-4757-6568-7 · Zbl 0915.52003 · doi:10.1007/978-1-4757-6568-7 |
| [21] | Cucker, F., Smale, S.: Emergent behavior in flocks. IEEE Trans. Autom. Control 52(5), 852-862 (2007). doi:10.1109/tac.2007.895842 · Zbl 1366.91116 · doi:10.1109/tac.2007.895842 |
| [22] | Cucker, F., Smale, S.: On the mathematics of emergence. Jpn. J. Math. 2(1), 197-227 (2007). doi:10.1007/s11537-007-0647-x · Zbl 1166.92323 · doi:10.1007/s11537-007-0647-x |
| [23] | Damelin, S.B., Grabner, P.J.: Energy functionals, numerical integration and asymptotic equidistribution on the sphere. J. Complex. 19(3), 231-246 (2003). doi:10.1016/s0885-064x(02)00006-7 · Zbl 1043.65049 · doi:10.1016/s0885-064x(02)00006-7 |
| [24] | Diananda, P.H.: Notes on two lemmas concerning the Epstein zeta function. Proc. Glasg. Math. Assoc. 6, 202-204 (1964). doi:10.1017/s2040618500035036 · Zbl 0128.04501 · doi:10.1017/s2040618500035036 |
| [25] | Economou, E.N.: Green’s Functions in Quantum Physics, vol. 7. Springer, Berlin (1983). doi:10.1007/978-3-662-02369-3 · doi:10.1007/978-3-662-02369-3 |
| [26] | Ennola, V.: A lemma about the Epstein zeta function. Proc. Glasg. Math. Assoc. 6, 198-201 (1964). doi:10.1017/s2040618500035024 · Zbl 0128.04402 · doi:10.1017/s2040618500035024 |
| [27] | Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23, 298-305 (1973) · Zbl 0265.05119 |
| [28] | Ganapati, V., Miller, O.D., Yablonovitch, E.: Light trapping textures designed by electromagnetic optimization for subwavelength thick solar cells. IEEE J. Photovol. 4(1), 175-182 (2014). doi:10.1109/jphotov.2013.2280340 · doi:10.1109/jphotov.2013.2280340 |
| [29] | Ghosh, A., Boyd, S.: Growing well-connected graphs. In: Proceedings of the IEEE Conference Decision and Control, pp. 6605-6611 (2006). doi:10.1109/cdc.2006.377282 · Zbl 1338.15026 |
| [30] | Ghosh, A., Boyd, S.: Upper bounds on algebraic connectivity via convex optimization. Linear Algebra Appl. 418, 693-707 (2006). doi:10.1016/j.laa.2006.03.006 · Zbl 1105.05045 · doi:10.1016/j.laa.2006.03.006 |
| [31] | Ghosh, A., Boyd, S., Saberi, A.: Minimizing effective resistance of a graph. SIAM Rev. 50(1), 37-66 (2008). doi:10.1137/050645452 · Zbl 1134.05057 · doi:10.1137/050645452 |
| [32] | Godsil, C.D., Mohar, B.: Walk generating functions and spectral measures of infinite graphs. Linear Algebra Appl. 107, 191-206 (1988). doi:10.1016/0024-3795(88)90245-5 · Zbl 0654.05054 · doi:10.1016/0024-3795(88)90245-5 |
| [33] | Kao, C.Y., Lai, R., Osting, B.: Maximization of Laplace-Beltrami eigenvalues on closed Riemannian surfaces. ESAIM Control Optim. Calc. Var. (2016). doi:10.1051/cocv/2016008 · Zbl 1362.35199 |
| [34] | Kirr, E., Weinstein, M.I.: Parametrically excited Hamiltonian partial differential equations. SIAM J. Appl. Math. 33(1), 16-52 (2001). doi:10.1137/s0036141099363456 · Zbl 1097.35524 · doi:10.1137/s0036141099363456 |
| [35] | Kirr, E., Weinstein, M.I.: Metastable states in parametrically excited multimode Hamiltonian systems. Commun. Math. Phys. 236(2), 335-372 (2003). doi:10.1007/s00220-003-0820-x · Zbl 1033.81027 · doi:10.1007/s00220-003-0820-x |
| [36] | Lin, L., Saad, Y., Yang, C.: Approximating spectral densities of large matrices. SIAM Rev. 58(1), 34-65 (2016). doi:10.1137/130934283 · Zbl 1338.15026 · doi:10.1137/130934283 |
| [37] | Luxburg, U.V.: A tutorial on spectral clustering. Stat. Comput. 17(4), 395-416 (2007). doi:10.1007/s11222-007-9033-z · doi:10.1007/s11222-007-9033-z |
| [38] | Marcotte, E., Stillinger, F.H., Torquato, S.: Unusual ground states via monotonic convex pair potentials. J. Chem. Phys. 134(16), 164,105 (2011). doi:10.1063/1.3576141 · doi:10.1063/1.3576141 |
| [39] | Matoušek, J.: Geometric Discrepancy: An Illustrated Guide. Springer, Berlin (1999). doi:10.1007/978-3-642-03942-3 · Zbl 0930.11060 · doi:10.1007/978-3-642-03942-3 |
| [40] | Miller, O.D.: Photonic design: from fundamental solar cell physics to computational inverse design. arXiv: 1308.0212 (2013) · Zbl 1097.35524 |
| [41] | Miller, O.D., Yablonovitch, E.: Photon extraction: the key physics for approaching solar cell efficiency limits. In: Proceedings of the SPIE 8808, Active Photonic Materials, p. 880807 (2013). doi:10.1117/12.2024592 · Zbl 1166.92323 |
| [42] | Mohar, B.: The Laplacian spectrum of graphs. In: Alavi, Y., Chartrand, G., Oellermann, O.R., Schwenk, A.J. (eds.) Graph Theory, Combinatorics, and Applications, vol. 2, pp. 871-898. Wiley (1991) · Zbl 1366.91116 |
| [43] | Mohar, B., Woess, W.: A survey on spectra of infinite graphs. Bull. Lond. Math. Soc. 21(3), 209-234 (1989). doi:10.1112/blms/21.3.209 · Zbl 0645.05048 · doi:10.1112/blms/21.3.209 |
| [44] | Montgomery, H.L.: Minimal theta functions. Glasg. Math. J. 30(1), 75-85 (1988). doi:10.1017/s0017089500007047 · Zbl 0639.10017 · doi:10.1017/s0017089500007047 |
| [45] | Motsch, S., Tadmor, E.: A new model for self-organized dynamics and its flocking behavior. J. Stat. Phys. 144(5), 923-947 (2011). doi:10.1007/s10955-011-0285-9 · Zbl 1230.82037 · doi:10.1007/s10955-011-0285-9 |
| [46] | Olfati-Saber, R., Fax, A., Murray, R.M.: Consensus and cooperation in networked multi-agent systems. Proc. IEEE 95(1), 215-233 (2007). doi:10.1109/jproc.2006.887293 · Zbl 1376.68138 · doi:10.1109/jproc.2006.887293 |
| [47] | Osting, B., Brune, C., Osher, S.: Enhanced statistical rankings via targeted data collection. JMLR W&CP 28(1), 489-497 (2013) |
| [48] | Osting, B., Brune, C., Osher, S.: Optimal data collection for informative rankings expose well-connected graphs. J. Mach. Learn. Res. 15, 2981-3012 (2014) · Zbl 1319.62046 |
| [49] | Osting, B., Marzuola, J.L., Cherkaev, E.: An isoperimetric inequality for integral operators on flat tori. Ill. J. Math. 59(3), 773-793 (2015). http://projecteuclid.org/euclid.ijm/1475266407 · Zbl 1359.58017 |
| [50] | Osting, B., Weinstein, M.I.: Emergence of periodic structure from maximizing the lifetime of a bound state coupled to radiation. SIAM J. Multiscale Model. Simul. 9(2), 654-685 (2011). doi:10.1137/100813221 · Zbl 1227.49049 · doi:10.1137/100813221 |
| [51] | Purcell, E.M.: Spontaneous emission probabilities at radio frequencies. Phys. Rev. 69, 681 (1946) · doi:10.1103/PhysRev.69.37 |
| [52] | Purcell, E.M.: Research in nuclear magnetism. Science 118(3068), 431-436 (1953) · Zbl 0103.27602 |
| [53] | Rankin, R.A.: A minimum problem for the Epstein zeta-function. In: Proceedings of the Glasgow Mathematical Association, vol. 1, pp. 149-158 (1953). doi:10.1017/s2040618500035668 · Zbl 0052.28005 |
| [54] | Saff, E.B., Kuijlaars, A.B.J.: Distributing many points on a sphere. Math. Intell. 19(1), 5-11 (1997). doi:10.1007/bf03024331 · Zbl 0901.11028 · doi:10.1007/bf03024331 |
| [55] | Shannon, C.E.: A mathematical theory of communication. ACM SIGMOBILE Mob. Comput. Commun. Rev. 5(1), 3-55 (2001) · doi:10.1145/584091.584093 |
| [56] | Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888-905 (2000). doi:10.1109/34.868688 · doi:10.1109/34.868688 |
| [57] | Singer, A.: From graph to manifold Laplacian: the convergence rate. Appl. Comput. Harmonic Anal. 21(1), 128-134 (2006). doi:10.1016/j.acha.2006.03.004 · Zbl 1095.68102 · doi:10.1016/j.acha.2006.03.004 |
| [58] | Smale, S.: Mathematical problems for the next century. Math. Intell. 20(2), 7-15 (1998). doi:10.1007/bf03025291 · Zbl 0947.01011 · doi:10.1007/bf03025291 |
| [59] | Sun, J., Boyd, S., Xiao, L., Diaconis, P.: The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. SIAM Rev. 48(4), 681-699 (2006). doi:10.1137/s0036144504443821 · Zbl 1109.60324 · doi:10.1137/s0036144504443821 |
| [60] | Thomson, J.J.: On the structure of the atom: an investigation of the stability and periods of oscillation of a number of corpuscles arranged at equal intervals around the circumference of a circle; with application of the results to the theory of atomic structure. Philos. Mag. Ser. 6 7(39), 237-265 (1904). doi:10.1080/14786440409463107 · JFM 35.0790.01 · doi:10.1080/14786440409463107 |
| [61] | Torquato, S., Stillinger, F.H.: Jammed hard-particle packings: from Kepler to Bernal and beyond. Rev. Mod. Phys. 82(3), 2633-2672 (2010). doi:10.1103/revmodphys.82.2633 · doi:10.1103/revmodphys.82.2633 |
| [62] | Tóth, L.F.: Regular Figures. Pergamon Press, Oxford (1964) · Zbl 0134.15705 |
| [63] | Van Hove, L.: The occurrence of singularities in the elastic frequency distribution of a crystal. Phys. Rev. 89(6), 1189-1193 (1953). doi:10.1103/physrev.89.1189 · Zbl 0050.23605 · doi:10.1103/physrev.89.1189 |
| [64] | Wendland, H.: Scattered Data Approximation. Cambridge University Press, Cambridge (2004). doi:10.1017/cbo9780511617539 · Zbl 1185.65022 · doi:10.1017/cbo9780511617539 |
| [65] | Whyte, L.L.: Unique arrangements of points on a sphere. Am. Math. Mon. 59(9), 606-611 (1952). doi:10.2307/2306764 · Zbl 0048.13602 · doi:10.2307/2306764 |
| [66] | Yablonovitch, E.: Inhibited spontaneous emission in solid-state physics and electronics. Phys. Rev. Lett. 58(20), 2059-2062 (1987). doi:10.1103/physrevlett.58.2059 · doi:10.1103/physrevlett.58.2059 |
| [67] | Yu, Z., Raman, A., Fan, S.: Fundamental limit of nanophotonic light trapping in solar cells. Proc. Natl. Acad. Sci. 107(41), 17491-17496 (2010). doi:10.1073/pnas.1008296107 · doi:10.1073/pnas.1008296107 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
