Uncontrollable computational growth in theoretical physics

DOI10.1007/BF00670329MaRDI QIDQ1071512zbMATH OpenOpenAlexFDO

Authors R. Cuykendall

Publication date 1985

Published in International Journal of Theoretical Physics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00670329

zbMATH Keywords

distortion among time-weighted runsKolmogorov conditional informationQCD simulationquantum chromodynamicssynchronous parallel computationunavoidable limitations to computingvery-large-scale Monte Carlo simulationsVLSI areaVLSI computation

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Monte Carlo methods (65C05) General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Rate-distortion theory in information and communication theory (94A34)

Review text

Some new results in the theory of synchronous parallel computation indicate there may be fundamentally unavoidable limitations to computing in certain kinds of large computational problems arising naturally in science and engineering. These limitations are in the nature of uncontrolled growth (discontinuous jumps) in computation times under fixed programming schemes, and arise for computations allowing arbitrary (uniform) inputs over \(F^ n\) for sufficiently large n, where F is a finite field. Instances of such discontinuity may appear, for example, in very-large-scale Monte Carlo simulations, such as those being contemplated for carrying out quantum chromodynamics (QCD) computations on lattices of substantially larger size than is now practicable. In this case, the QCD simulation may encounter abnormally (and unexplained) long run times on particular internally generated updates, resulting in distortion among time-weighted runs. The mechanism of these updates is believed to satisfy our necessary assumption for fixed encodings over uniform inputs.

Recommendations

• scientific article; zbMATH DE number 3958735
• Status and prospects of the computational approach to high-energy physics
• scientific article; zbMATH DE number 1206092
• scientific article; zbMATH DE number 4195172
• Computations with uncertain time constraints: effects on parallelism and universality

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• A Theory of Program Size Formally Identical to Information Theory
• Computational speed-up by effective operators
• Diversity of speed-ups and embeddability in computational complexity
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3407149 (Why is no real title available?)
• Logical basis for information theory and probability theory
• On Effective Procedures for Speeding Up Algorithms
• On Relating Time and Space to Size and Depth
• On size vs. efficiency for programs admitting speed-ups
• Relations Among Complexity Measures
• The network complexity and the Turing machine complexity of finite functions
• Uniformly reasonable source encoding is often practically impossible

Cited in

(3)

• Computations with uncertain time constraints: effects on parallelism and universality
• scientific article; zbMATH DE number 3915681 (Why is no real title available?)
• Probabilistic arithmetic. I: Numerical methods for calculating convolutions and dependency bounds

This page was built for publication: Uncontrollable computational growth in theoretical physics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1071512)