×

Reducing memory requirements in scientific computing and optimal control. (English) Zbl 1337.65052

Carraro, Thomas (ed.) et al., Multiple shooting and time domain decomposition methods. MuS-TDD, Heidelberg, Germany, May 6–8, 2013. Cham: Springer (ISBN 978-3-319-23320-8/hbk; 978-3-319-23321-5/ebook). Contributions in Mathematical and Computational Sciences 9, 263-287 (2015).
Summary: In high accuracy numerical simulations and optimal control of time-dependent processes, often both many timesteps and fine spatial discretizations are needed. Adjoint gradient computation, or post-processing of simulation results, requires the storage of the solution trajectories over the whole time, if necessary together with the adaptively refined spatial grids. In this paper we discuss various techniques to reduce the memory requirements, focusing first on the storage of the solution data, which are typically double precision floating point values. We highlight advantages and disadvantages of the different approaches. Moreover, we present an algorithm for the efficient storage of adaptively refined, hierarchic grids, and the integration with the compressed storage of solution data.
For the entire collection see [Zbl 1333.65003].

MSC:

65K10 Numerical optimization and variational techniques
49J20 Existence theories for optimal control problems involving partial differential equations
49M25 Discrete approximations in optimal control
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alliez, P., Desbrun, M.: Progressive compression for lossless transmission of triangle meshes. In: Proceedings of 28th Annual Conference on Computer Graphics and Interactive Techniques, pp. 195-202. ACM (2001)
[2] Alliez, P., Gotsman, C.: Recent advances in compression of 3d meshes. In: Dodgson, N., Floater, M., Sabin, M. (eds.) Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, pp. 3-26. Springer, Berlin/Heidelberg (2005). doi:10.1007/3-540-26808-1_1. doi:10.1007/3-540-26808-1_1 · Zbl 1065.65025
[3] Avilés, M.; Morán, F.; García, N., Progressive lower trees of wavelet coefficients: efficient spatial and SNR scalable coding of 3D models, In: Advances in Mulitmedia Information Processing-PCM, 2005, 61-72 (2005)
[4] Bank, R. E.; Sherman, A. H.; Weiser, A.; Stepleman, R., Some refinement algorithms and data structures for regular local mesh refinement, Scientific Computing. Applications of Mathematics and Computing to the Physical Sciences (1983), Amsterdam: IMACS/North-Holland, Amsterdam
[5] Becker, R.; Rannacher, R., An optimal control approach to a posteriori error estimation in finite element methods, Acta Numerica, 10, 1, 1-102 (2001) · Zbl 1105.65349
[6] Becker, R., Meidner, D., Vexler, B.: Efficient numerical solution of parabolic optimization problems by finite element methods. Optim. Methods Softw. 22(5), 813-833 (2007). doi:10.1080/10556780701228532 · Zbl 1135.35317
[7] Burtscher, M.; Ratanaworabhan, P., FPC: a high-speed compressor for double-precision floating-point data, IEEE Trans. Comput., 58, 1, 18-31 (2009) · Zbl 1367.65209 · doi:10.1109/TC.2008.131
[8] Castrillón-Candás, J. E.; Amaratunga, K., Spatially adapted multiwavelets and sparse representation of integral equations on general geometries, SIAM J. Sci. Comput., 24, 5, 1530-1566 (2003) · Zbl 1042.65112 · doi:10.1137/S1064827501371238
[9] Cignoni, P.; Rocchini, C.; Scopigno, R., Metro: measuring error on simplified surfaces (1996), Paris, France: Tech. Rep, Paris, France
[10] Comas, A.: Time-domain decomposition preconditioners for the solution of discretized parabolic optimal control problems. Ph.D. thesis, Rice University (2005)
[11] Dahmen, W., Wavelet methods for PDEs – some recent developments, J. Comput. Appl. Math., 128, 1, 133-185 (2001) · Zbl 0974.65101 · doi:10.1016/S0377-0427(00)00511-2
[12] Denis, L.; Satti, S.; Munteanu, A.; Cornelis, J.; Schelkens, P., Scalable intraband and composite wavelet-based coding of semiregular meshes, IEEE Trans. Multimedia, 12, 8, 773-789 (2010) · doi:10.1109/TMM.2010.2058094
[13] Deuflhard, P.; Bornemann, F., Scientific Computing with Ordinary Differential Equations (2002), Berlin: Springer, Berlin · Zbl 1001.65071
[14] Deuflhard, P.; Nowak, U.; Deuflhard, P.; Engquist, B., Extrapolation integrators for quasilinear implicit ODEs, Large Scale Scientific Computing. Progress in Scientific Computing, 37-50 (1987), Basel: Birkhäuser, Basel · Zbl 0617.65078 · doi:10.1007/978-1-4684-6754-3_3
[15] Deuflhard, P.; Leinen, P.; Yserentant, H., Concepts of an adaptive hierarchical finite element code, IMPACT Comput. Sci. Eng., 1, 1, 3-35 (1989) · Zbl 0706.65111 · doi:10.1016/0899-8248(89)90018-9
[16] Goeman, B., Vandierendonck, H., De Bosschere, K.: Differential FCM: increasing value prediction accuracy by improving table usage efficiency. In: The 7th International Symposium on High-Performance Computer Architecture, 2001. HPCA, pp. 207-216. IEEE (2001)
[17] Götschel, S., Weiser, M.: Lossy compression for PDE-constrained optimization: Adaptive error control. ZIB Report, pp. 13-27 (2013) · Zbl 1333.49043
[18] Götschel, S.; Weiser, M.; Schiela, A.; Dedner, A.; Flemisch, B.; Klöfkorn, R., Solving optimal control problems with the Kaskade 7 finite element toolbox, Advances in DUNE, 101-112 (2012), New York: Springer, New York · doi:10.1007/978-3-642-28589-9_8
[19] Götschel, S.; Nagaiah, C.; Kunisch, K.; Weiser, M., Lossy compression in optimal control of cardiac defibrillation, J. Sci. Comput., 60, 1, 35-59 (2014) · Zbl 1304.92069 · doi:10.1007/s10915-013-9785-x
[20] Griewank, A., Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation, Optim. Methods Softw., 1, 1, 35-54 (1992) · doi:10.1080/10556789208805505
[21] Griewank, A.; Walther, A., Algorithm 799: revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation, ACM Trans. Math. Softw., 26, 1, 19-45 (2000) · Zbl 1137.65330 · doi:10.1145/347837.347846
[22] Griewank, A.; Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation (2008), Philadelphia: SIAM, Philadelphia · Zbl 1159.65026 · doi:10.1137/1.9780898717761
[23] Heinkenschloss, M., A time-domain decomposition iterative method for the solution of distributed linear quadratic optimal control problems, J. Comput. Appl. Math., 173, 1, 169-198 (2005) · Zbl 1075.65091 · doi:10.1016/j.cam.2004.03.005
[24] Hesse, H.K.: Multiple shooting and mesh adaptation for PDE constrained optimization problems. Ph.D. thesis, University Heidelberg (2008) · Zbl 1149.65308
[25] Hesse, H.K., Kanschat, G.: Mesh adaptive multiple shooting for partial differential equations. part I: linear quadratic optimal control problems. J. Numer. Math. 17(3), 195-217 (2009) · Zbl 1177.65092
[26] Heuveline, V., Walther, A.: Online checkpointing for parallel adjoint computation in PDEs: application to goal-oriented adaptivity and flow control. In: Euro-Par 2006 Parallel Processing, pp. 689-699. Springer, Berlin (2006)
[27] Hinze, M.; Sternberg, J., A-revolve: an adaptive memory-reduced procedure for calculating adjoints; with an application to computing adjoints of the instationary Navier-Stokes system, Optim. Methods Softw., 20, 6, 645-663 (2005) · Zbl 1086.49024 · doi:10.1080/10556780410001684158
[28] Hinze, M.; Volkwein, S., Error estimates for abstract linear-quadratic optimal control problems using proper orthogonal decomposition, Comput. Optim. Appl., 39, 319-345 (2008) · Zbl 1191.49040 · doi:10.1007/s10589-007-9058-4
[29] Hinze, M.; Pinnau, R.; Ulbrich, M.; Ulbrich, S., Optimization with PDE Constraints (2009), Berlin: Springer, Berlin · Zbl 1167.49001
[30] Ibarria, L., Lindstrom, P., Rossignac, J., Szymczak, A.: Out-of-core compression and decompression of large n-dimensional scalar fields. In: Computer Graphics Forum, vol. 22, pp. 343-348. Wiley Online Library (2003)
[31] Isenburg, M.: Compressing polygon mesh connectivity with degree duality prediction. In: Graphics Interface Conference Proceedings, pp. 161-170 (2002)
[32] Isenburg, M., Snoeyink, J.: Mesh collapse compression. In: Proceedings of SIBGRAPI’99, pp. 27-28 (1999)
[33] Isenburg, M., Snoeyink, J.: Early-split coding of triangle mesh connectivity. In: Graphics Interface Proceedings, pp. 89-97. Canadian Information Processing Society, Toronto, ON (2006)
[34] Ito, K.; Kunisch, K., Receding horizon optimal control for infinite dimensional systems, ESAIM Control Optim. Calc. Var., 8, 1, 741-760 (2002) · Zbl 1066.49020 · doi:10.1051/cocv:2002032
[35] Iverson, J., Kamath, C., Karypis, G.: Fast and effective lossy compression algorithms for scientific datasets. In: Euro-Par 2012 Parallel Processing, pp. 843-856. Springer, Berlin (2012)
[36] JavaView Homepage: www.javaview.de (2014)
[37] Jörres, C.; Vossen, G.; Herty, M., On an inexact gradient method using proper orthogonal decomposition for parabolic optimal control problems, Comput. Optim. Appl., 55, 2, 1-10 (2013) · Zbl 1272.49058 · doi:10.1007/s10589-013-9533-z
[38] Kälberer, F.; Polthier, K.; Reitebuch, U.; Wardetzky, M., Freelence - coding with free valences, Comput. Graph. Forum, 24, 3, 469-478 (2005) · doi:10.1111/j.1467-8659.2005.00872.x
[39] Kälberer, F., Polthier, K., von Tycowicz, C.: Lossless compression of adaptive multiresolution meshes. In: Proceedings of Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI), vol. 22 (2009)
[40] Kammann, E.; Tröltzsch, F.; Volkwein, S., A method of a-posteriori error estimation with application to proper orthogonal decomposition (2011), Rep: Tech, Rep
[41] Khodakovsky, A., Guskov, I.: Compression of normal meshes. In: Geometric Modeling for Scientific Visualization, pp. 189-206. Springer, Berlin (2003)
[42] Khodakovsky, A., Schröder, P., Sweldens, W.: Progressive geometry compression. In: SIGGRAPH’00 Proceedings, pp. 271-278 (2000)
[43] Kunisch, K.; Volkwein, S., Galerkin proper orthogonal decomposition methods for parabolic problems, Numer. Math., 90, 117-148 (2001) · Zbl 1005.65112 · doi:10.1007/s002110100282
[44] Kunisch, K., Wagner, M.: Optimal control of the bidomain system (I): The monodomain approximation with the Rogers-McCulloch model. Nonlinear Anal. Real World Appl. 13(4), 1525-1550 (2012). doi:10.1016/j.nonrwa.2011.11.003. http://www.sciencedirect.com/science/article/pii/S1468121811003099 · Zbl 1256.49009
[45] Lakshminarasimhan, S., Shah, N., Ethier, S., Klasky, S., Latham, R., Ross, R., Samatova, N.F.: Compressing the incompressible with ISABELA: in-situ reduction of spatio-temporal data. In: Euro-Par 2011 Parallel Processing, pp. 366-379. Springer, Berlin (2011)
[46] Lakshminarasimhan, S.; Shah, N.; Ethier, S.; Ku, S. H.; Chang, C. S.; Klasky, S.; Latham, R.; Ross, R.; Samatova, N. F., ISABELA for effective in situ compression of scientific data, Concurr. Comput. Pract. Exper., 25, 524-540 (2013) · doi:10.1002/cpe.2887
[47] Lee, H., Alliez, P., Desbrun, M.: Angle-analyzer: a triangle-quad mesh codec. In: Drettakis, G., Seidel, H.-P. (eds.) Eurographics 2002 Conference Proceedings, pp. 383-392 (2002)
[48] Lindstrom, P., Isenburg, M.: Fast and efficient compression of floating-point data. IEEE Trans. Vis. Comput. Graph. 12(5), 1245-1250 (2006). doi:10.1109/TVCG.2006.143
[49] Martin, G.: Range encoding: an algorithm for removing redundancy from a digitised message. In: Presented at Video & Data Recording Conference, Southampton (1979)
[50] Nagaiah, C., Kunisch, K., Plank, G.: Numerical solution for optimal control of the reaction-diffusion equations in cardiac electrophysiology. Comput. Optim. Appl. 49, 149-178 (2011). doi:10.1007/s10589-009-9280-3. doi:10.1007/s10589-009-9280-3 · Zbl 1226.49024
[51] Nielsen, B. F.; Ruud, T. S.; Lines, G. T.; Tveito, A., Optimal monodomain approximations of the bidomain equations, Appl. Math. Comput., 184, 2, 276-290 (2007) · Zbl 1115.92005 · doi:10.1016/j.amc.2006.05.158
[52] Nocedal, J.; Wright, S. J., Numerical Optimization (2006), New York: Springer, New York · Zbl 1104.65059
[53] Payan, F.; Antonini, M., An efficient bit allocation for compressing normal meshes with an error-driven quantization, Comput. Aided Geom. Des., 22, 5, 466-486 (2005) · Zbl 1087.65523 · doi:10.1016/j.cagd.2005.04.001
[54] Peng, J., Kim, C.S., Jay Kuo, C.C.: Technologies for 3d mesh compression: a survey. J. Vis. Commun. Image Represent. 16(6), 688-733 (2005). doi:10.1016/j.jvcir.2005.03.001. doi:10.1016/j.jvcir.2005.03.001
[55] Rogers, J. M.; McCulloch, A. D., A collocation-Galerkin finite element model of cardiac action potential propagation, IEEE Trans. Biomed. Eng., 41, 743-757 (1994) · doi:10.1109/10.310090
[56] Rossignac, J., Edgebreaker: connectivity compression for triangle meshes, IEEE Trans. Vis. Comput. Graph., 5, 47-61 (1999) · doi:10.1109/2945.764870
[57] Sazeides, Y., Smith, J.E.: The predictability of data values. In: Proceedings of 30th Annual IEEE/ACM International Symposium on Microarchitecture, 1997, pp. 248-258. IEEE (1997)
[58] Schröder, P., Sweldens, W.: Spherical wavelets: efficiently representing functions on the sphere. In: SIGGRAPH ‘95 Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, pp. 161-172. ACM (1995) · Zbl 0970.42024
[59] Shafaat, T. M.; Baden, S. B.; Kågström, B.; Elmroth, E.; Dongarra, J.; Wasniewski, J., A method of adaptive coarsening for compressing scientific datasets, Applied Parallel Computing. State of the Art in Scientific Computing. 8th International Workshop, PARA 2006, Umeå, Sweden, 18-21 June 2006, Revised Selected Papers. Lecture Notes in Computer Science, 774-780 (2007), New York: Springer, New York
[60] Shannon, C. E., A mathematical theory of communication, Bell Syst. Tech. J., 27, 379-423 (1948) · Zbl 1154.94303 · doi:10.1002/j.1538-7305.1948.tb01338.x
[61] Shapiro, J. M., Embedded image coding using zerotrees of wavelet coefficients, IEEE Trans. Signal Process., 41, 3445-3462 (1993) · Zbl 0841.94020 · doi:10.1109/78.258085
[62] Sternberg, J.; Hinze, M., A memory-reduced implementation of the Newton-CG method in optimal control of nonlinear time-dependent PDEs, Optim. Methods Softw., 25, 4, 553-571 (2010) · Zbl 1205.49039 · doi:10.1080/10556780903027187
[63] Stumm, P.; Walther, A., Multi-stage approaches for optimal offline checkpointing, SIAM J. Sci. Comput., 31, 3, 1946-1967 (2009) · Zbl 1194.65084 · doi:10.1137/080718036
[64] Stumm, P.; Walther, A., New algorithms for optimal online checkpointing, SIAM J. Sci. Comput., 32, 1, 836-854 (2010) · Zbl 1214.65038 · doi:10.1137/080742439
[65] Sweldens, W., The lifting scheme: a construction of second generation wavelets, SIAM J. Math. Anal., 29, 2, 511-546 (1998) · Zbl 0911.42016 · doi:10.1137/S0036141095289051
[66] Szymczak, A.: Optimized edgebreaker encoding for large and regular triangle meshes. In: DCC ‘02 Proceedings, p. 472. IEEE Computer Society, Washington, DC (2002)
[67] Teran, R.I., Thole, C.A., Lorentz, R.: New developments in the compression of LS-DYNA simulation results using FEMZIP. In: 6th European LS-DYNA Users’ Conference (2007). https://www.dynalook.com/european-conf-2007/new-developments-in-the-compression-of-ls-dyna.pdf
[68] Thole, C.A.: Compression of LS-DYNA3D^TM simulation results using FEMZIP©. 3. LS-DYNA Anwenderforum (2004)
[69] Touma, C., Gotsman, C.: Triangle mesh compression. In: Graphics Interface Conference Proceedings, pp. 26-34 (1998)
[70] Tröltzsch, F.; Volkwein, S., POD a-posteriori error estimates for linear-quadratic optimal control problems, Comput. Optim. Appl., 44, 83-115 (2009) · Zbl 1189.49050 · doi:10.1007/s10589-008-9224-3
[71] Tutte, W., A census of planar triangulations, Can. J. Math., 14, 21-38 (1962) · Zbl 0103.39603 · doi:10.4153/CJM-1962-002-9
[72] Unat, D.; Hromadka, T.; Baden, S., An adaptive sub-sampling method for in-memory compression of scientific data (2009), In: Data Compression Conference, In · doi:10.1109/DCC.2009.65
[73] Valette, S.; Prost, R., Wavelet-based progressive compression scheme for triangle meshes: wavemesh, IEEE Trans. Vis. Comput. Graph., 10, 2, 123-129 (2004) · doi:10.1109/TVCG.2004.1260764
[74] van der Vorst, H. A., Bi-CGSTAB: a fast and smoothly converging variant of bi-cg for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 13, 631-644 (1994) · Zbl 0761.65023 · doi:10.1137/0913035
[75] von Tycowicz, C., Kälberer, F., Polthier, K.: Context-based coding of adaptive multiresolution meshes. Comput. Graph. Forum 30(8), 2231-2245 (2011). doi:10.1111/j.1467-8659.2011.01972.x. doi:10.1111/j.1467-8659.2011.01972.x
[76] Walther, A.: Program reversal schedules for single-and multi-processor machines. Ph.D. thesis, Institute of Scientific Computing, Technical University Dresden, Germany (1999)
[77] Wang, Q.; Moin, P.; Iaccarino, G., Minimal repetition dynamic checkpointing algorithm for unsteady adjoint calculation, SIAM J. Sci. Comput., 31, 4, 2549-2567 (2009) · Zbl 1196.65050 · doi:10.1137/080727890
[78] Weiser, M.; Götschel, S., State trajectory compression for optimal control with parabolic PDEs, SIAM J. Sci. Comput., 34, 1, A161-A184 (2012) · Zbl 1237.49040 · doi:10.1137/11082172X
[79] Yserentant, H., On the multi-level splitting of finite element spaces, Numer. Math., 49, 4, 379-412 (1986) · Zbl 0608.65065 · doi:10.1007/BF01389538
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.