ITR: Statistical Physics and Computational Complexity

ITR：统计物理和计算复杂性

• 批准号: 0219292
• 负责人: Mark Bowick
• 金额: $ 47.4万
• 依托单位: Syracuse University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-08-01 至 2007-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0219292&HistoricalAwards=false
• 关键词: ITR; Statistical; Physics; Computational; Complexity

This award under the Information Technology Research initiative explores and strengthens connections between computer science and the physics of complex systems, addressing the important examples of membranes and disordered materials from condensed matter physics. The proposed research brings these disciplines closer together by recognizing that not only are novel algorithmic tools crucial for modeling complex physical systems, but that there are fundamental links between the physical properties of the system and the computational complexity of the simulation. This project will also train students and researchers in this area at the interface between condensed matter theory and information technology and provide simulation software components for the research community. Many of the challenges in sciences such as physics and biology are problems in understanding the behavior of a very large number of strongly interacting degrees of freedom, where the macroscopic behavior is determined by the competition between local ordering and disordering effects, including temperature, heterogeneities, and geometry. Examples abound in the both the classical and quantum world, including vortex lines in superconductors, strongly correlated electrons in disordered solids, and fluctuating membranes, as seen in cells and artificial colloidal structures. Describing the phases and transitions in these systems relies upon being able to build up the large-scale behavior from microscopic models. This is quite challenging for conventional simulations. The intent here is to draw on ideas from computer science to develop new algorithms and to identify universal features using extensive simulations. In turn these features will be used to develop new simulation methods and analytical understanding. This project will focus on specific areas in condensed matter physics that are of direct experimental relevance and raise general algorithmic questions:The PIs will study the phase diagram of realistic models of physical membranes, with important applications to biological membranes.The PIs will explore the defect structure of crystals on topographies of fixed curvature, such as a crystal on the surface of a sphere, and more complex geometries. This work has direct relevance to the rich physics of colloidosomes, spherical viruses and other systems currently studied in many laboratories. This work will rely on combining knowledge about small-scale defects and long wavelength elasticity and exploring optimization algorithms.The PIs will investigate the phases of a class of disordered classical (e.g., vortex lines in superconductors) and quantum (interacting electrons in disordered solids) disordered systems that can be studied simultaneously by the same numerical algorithm.The PIs will explore the connection between polynomial time optimization algorithm and physical theories of disordered materials. This includes the development of new approaches to explain the timing of algorithms by adapting physical concepts of phases and correlation lengths to their nonphysical dynamics.The achievement of the scientific goals for specific physical systems and algorithmic studies will be closely linked with more general benefits:The training of undergraduate and graduate students and postdoctoral researchers who will have the expertise and inclination to work at the bridge between statistical physics and computer science.Building a common expertise and suggesting potential collaborations in the computer science and physics communities.Software development, in three parts (problem generators, solvers, and data analyzers), that can be adopted by researchers to solve related problems and for testing alternate computational approaches.%%%This award under the Information Technology Research initiative explores and strengthens connections between computer science and the physics of complex systems. The research enhances and builds connections between these disciplines by recognizing that not only are novel algorithmic tools crucial for modeling complex physical systems, but that there are fundamental links between the physical properties of the system and the computational complexity of the simulation. This project will also train students and researchers in this area at the interface between condensed matter theory and information technology and provide simulation software components for the research community. Many of the challenges in sciences such as physics and biology are problems in understanding the behavior of a very large number of strongly interacting degrees of freedom, where the macroscopic behavior is determined by the competition between local ordering and disordering effects, including temperature, heterogeneities, and geometry. Examples abound in the both the classical and quantum world, including vortex lines in superconductors, strongly correlated electrons in disordered solids, and fluctuating membranes, as seen in cells and artificial colloidal structures. Describing the phases and transitions in these systems relies upon being able to build up the large-scale behavior from microscopic models. This is quite challenging for conventional simulations. The intent here is to draw on ideas from computer science to develop new algorithms and to identify universal features using extensive simulations. In turn these features will be used to develop new simulation methods and analytical understanding. This project will focus on specific areas in condensed matter physics that are of direct experimental relevance and raise general algorithmic questions:The PIs will study the phase diagram of realistic models of physical membranes, with important applications to biological membranes.The PIs will explore the defect structure of crystals on topographies of fixed curvature, such as a crystal on the surface of a sphere, and more complex geometries. This work has direct relevance to the rich physics of colloidosomes, spherical viruses and other systems currently studied in many laboratories. This work will rely on combining knowledge about small-scale defects and long wavelength elasticity and exploring optimization algorithms.The PIs will investigate the phases of a class of disordered classical (e.g., vortex lines in superconductors) and quantum (interacting electrons in disordered solids) disordered systems that can be studied simultaneously by the same numerical algorithm.The PIs will explore the connection between polynomial time optimization algorithm and physical theories of disordered materials. This includes the development of new approaches to explain the timing of algorithms by adapting physical concepts of phases and correlation lengths to their nonphysical dynamics.The achievement of the scientific goals for specific physical systems and algorithmic studies will be closely linked with more general benefits:The training of undergraduate and graduate students and postdoctoral researchers who will have the expertise and inclination to work at the bridge between statistical physics and computer science.Building a common expertise and suggesting potential collaborations in the computer science and physics communities.Software development, in three parts (problem generators, solvers, and data analyzers), that can be adopted by researchers to solve related problems and for testing alternate computational approaches.***

该奖项隶属于信息技术研究计划，旨在探索和加强计算机科学与复杂系统物理学之间的联系，解决凝聚态物理学中膜和无序材料的重要例子。提出的研究通过认识到不仅新颖的算法工具对复杂物理系统建模至关重要，而且在系统的物理特性和模拟的计算复杂性之间存在基本联系，使这些学科更加紧密地联系在一起。该项目还将在凝聚态理论和信息技术之间的界面培训该领域的学生和研究人员，并为研究界提供模拟软件组件。物理学和生物学等科学中的许多挑战是理解大量强相互作用自由度的行为的问题，其中宏观行为是由局部有序和无序效应之间的竞争决定的，包括温度、异质性和几何。在经典和量子世界中都有很多这样的例子，包括超导体中的涡旋线，无序固体中的强相关电子，以及在细胞和人工胶体结构中看到的波动膜。描述这些系统中的阶段和转变依赖于能够从微观模型建立大规模行为。这对于传统模拟来说是相当具有挑战性的。这里的目的是利用计算机科学的思想来开发新的算法，并通过广泛的模拟来识别通用特征。反过来，这些特征将用于开发新的模拟方法和分析理解。该项目将专注于凝聚态物理中与直接实验相关的特定领域，并提出一般算法问题：pi将研究物理膜的现实模型的相图，并将其重要应用于生物膜。pi将探索固定曲率拓扑结构上的晶体缺陷结构，例如球体表面上的晶体，以及更复杂的几何形状。这项工作与目前在许多实验室研究的胶体体、球形病毒和其他系统的丰富物理学直接相关。这项工作将依赖于结合关于小尺度缺陷和长波弹性的知识，并探索优化算法。pi将研究一类无序的经典（例如，超导体中的涡旋线）和量子（无序固体中的相互作用电子）无序系统的相，这些系统可以通过相同的数值算法同时研究。pi将探索多项式时间优化算法与无序材料物理理论之间的联系。这包括通过调整相位和相关长度的物理概念来解释算法时序的新方法的发展。具体物理系统和算法研究的科学目标的实现将与更普遍的利益密切相关：培养本科生、研究生和博士后研究人员，他们将具有在统计物理学和计算机科学之间桥梁工作的专业知识和倾向。建立共同的专业知识，并建议在计算机科学和物理社区进行潜在的合作。软件开发，分为三个部分（问题产生者、解决者和数据分析者），研究人员可以采用这三个部分来解决相关问题和测试替代的计算方法。该奖项隶属于信息技术研究计划，旨在探索和加强计算机科学与复杂系统物理学之间的联系。该研究通过认识到不仅新颖的算法工具对复杂物理系统建模至关重要，而且在系统的物理特性和模拟的计算复杂性之间存在基本联系，增强并建立了这些学科之间的联系。该项目还将在凝聚态理论和信息技术之间的界面培训该领域的学生和研究人员，并为研究界提供模拟软件组件。物理学和生物学等科学中的许多挑战是理解大量强相互作用自由度的行为的问题，其中宏观行为是由局部有序和无序效应之间的竞争决定的，包括温度、异质性和几何。在经典和量子世界中都有很多这样的例子，包括超导体中的涡旋线，无序固体中的强相关电子，以及在细胞和人工胶体结构中看到的波动膜。描述这些系统中的阶段和转变依赖于能够从微观模型建立大规模行为。这对于传统模拟来说是相当具有挑战性的。这里的目的是利用计算机科学的思想来开发新的算法，并通过广泛的模拟来识别通用特征。反过来，这些特征将用于开发新的模拟方法和分析理解。该项目将专注于凝聚态物理中与直接实验相关的特定领域，并提出一般算法问题：pi将研究物理膜的现实模型的相图，并将其重要应用于生物膜。pi将探索固定曲率拓扑结构上的晶体缺陷结构，例如球体表面上的晶体，以及更复杂的几何形状。这项工作与目前在许多实验室研究的胶体体、球形病毒和其他系统的丰富物理学直接相关。这项工作将依赖于结合关于小尺度缺陷和长波弹性的知识，并探索优化算法。pi将研究一类无序的经典（例如，超导体中的涡旋线）和量子（无序固体中的相互作用电子）无序系统的相，这些系统可以通过相同的数值算法同时研究。pi将探索多项式时间优化算法与无序材料物理理论之间的联系。这包括通过调整相位和相关长度的物理概念来解释算法时序的新方法的发展。具体物理系统和算法研究的科学目标的实现将与更普遍的利益密切相关：培养本科生、研究生和博士后研究人员，他们将具有在统计物理学和计算机科学之间桥梁工作的专业知识和倾向。建立共同的专业知识，并建议在计算机科学和物理社区进行潜在的合作。软件开发，分为三个部分（问题产生者、解决者和数据分析者），研究人员可以采用这些部分来解决相关问题并测试替代的计算方法