-
A Study on Effect of Reference Knowledge Choice in Generating Technical Content Relevant to SAPPhIRE Model Using Large Language Model
Authors:
Kausik Bhattacharya,
Anubhab Majumder,
Amaresh Chakrabarti
Abstract:
Representation of systems using the SAPPhIRE model of causality can be an inspirational stimulus in design. However, creating a SAPPhIRE model of a technical or a natural system requires sourcing technical knowledge from multiple technical documents regarding how the system works. This research investigates how to generate technical content accurately relevant to the SAPPhIRE model of causality us…
▽ More
Representation of systems using the SAPPhIRE model of causality can be an inspirational stimulus in design. However, creating a SAPPhIRE model of a technical or a natural system requires sourcing technical knowledge from multiple technical documents regarding how the system works. This research investigates how to generate technical content accurately relevant to the SAPPhIRE model of causality using a Large Language Model, also called LLM. This paper, which is the first part of the two-part research, presents a method for hallucination suppression using Retrieval Augmented Generating with LLM to generate technical content supported by the scientific information relevant to a SAPPhIRE con-struct. The result from this research shows that the selection of reference knowledge used in providing context to the LLM for generating the technical content is very important. The outcome of this research is used to build a software support tool to generate the SAPPhIRE model of a given technical system.
△ Less
Submitted 29 June, 2024;
originally announced July 2024.
-
Development and Evaluation of a Retrieval-Augmented Generation Tool for Creating SAPPhIRE Models of Artificial Systems
Authors:
Anubhab Majumder,
Kausik Bhattacharya,
Amaresh Chakrabarti
Abstract:
Representing systems using the SAPPhIRE causality model is found useful in supporting design-by-analogy. However, creating a SAPPhIRE model of artificial or biological systems is an effort-intensive process that requires human experts to source technical knowledge from multiple technical documents regarding how the system works. This research investigates how to leverage Large Language Models (LLM…
▽ More
Representing systems using the SAPPhIRE causality model is found useful in supporting design-by-analogy. However, creating a SAPPhIRE model of artificial or biological systems is an effort-intensive process that requires human experts to source technical knowledge from multiple technical documents regarding how the system works. This research investigates how to leverage Large Language Models (LLMs) in creating structured descriptions of systems using the SAPPhIRE model of causality. This paper, the second part of the two-part research, presents a new Retrieval-Augmented Generation (RAG) tool for generating information related to SAPPhIRE constructs of artificial systems and reports the results from a preliminary evaluation of the tool's success - focusing on the factual accuracy and reliability of outcomes.
△ Less
Submitted 27 June, 2024;
originally announced June 2024.
-
Aaronson-Ambainis Conjecture Is True For Random Restrictions
Authors:
Sreejata Kishor Bhattacharya
Abstract:
In an attempt to show that the acceptance probability of a quantum query algorithm making $q$ queries can be well-approximated almost everywhere by a classical decision tree of depth $\leq \text{poly}(q)$, Aaronson and Ambainis proposed the following conjecture: let $f: \{ \pm 1\}^n \rightarrow [0,1]$ be a degree $d$ polynomial with variance $\geq ε$. Then, there exists a coordinate of $f$ with in…
▽ More
In an attempt to show that the acceptance probability of a quantum query algorithm making $q$ queries can be well-approximated almost everywhere by a classical decision tree of depth $\leq \text{poly}(q)$, Aaronson and Ambainis proposed the following conjecture: let $f: \{ \pm 1\}^n \rightarrow [0,1]$ be a degree $d$ polynomial with variance $\geq ε$. Then, there exists a coordinate of $f$ with influence $\geq \text{poly} (ε, 1/d)$.
We show that for any polynomial $f: \{ \pm 1\}^n \rightarrow [0,1]$ of degree $d$ $(d \geq 2)$ and variance $\text{Var}[f] \geq 1/d$, if $ρ$ denotes a random restriction with survival probability $\dfrac{\log(d)}{C_1 d}$, $$ \text{Pr} \left[f_ρ \text{ has a coordinate with influence} \geq \dfrac{\text{Var}[f]^2 }{d^{C_2}} \right] \geq \dfrac{\text{Var}[f] \log(d)}{50C_1 d}$$ where $C_1, C_2>0$ are universal constants. Thus, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.
△ Less
Submitted 21 February, 2024;
originally announced February 2024.
-
Exponential Separation Between Powers of Regular and General Resolution Over Parities
Authors:
Sreejata Kishor Bhattacharya,
Arkadev Chattopadhyay,
Pavel Dvořák
Abstract:
Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities is an outstanding problem that has received a lot of attention after its introduction by Raz and Tzamaret [Ann. Pure Appl. Log.'08]. Very recently, Efremenko, Garlík and Itsykson [ECCC'23] proved the first exponential lower bounds on the size of ResLin proofs that were…
▽ More
Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities is an outstanding problem that has received a lot of attention after its introduction by Raz and Tzamaret [Ann. Pure Appl. Log.'08]. Very recently, Efremenko, Garlík and Itsykson [ECCC'23] proved the first exponential lower bounds on the size of ResLin proofs that were additionally restricted to be bottom-regular. We show that there are formulas for which such regular ResLin proofs of unsatisfiability continue to have exponential size even though there exists short proofs of their unsatisfiability in ordinary, non-regular resolution. This is the first super-polynomial separation between the power of general ResLin and and that of regular ResLin for any natural notion of regularity.
Our argument, while building upon the work of Efremenko et al., uses additional ideas from the literature on lifting theorems.
△ Less
Submitted 23 February, 2024; v1 submitted 6 February, 2024;
originally announced February 2024.
-
Constructing Extreme Learning Machines with zero Spectral Bias
Authors:
Kaumudi Joshi,
Vukka Snigdha,
Arya Kumar Bhattacharya
Abstract:
The phenomena of Spectral Bias, where the higher frequency components of a function being learnt in a feedforward Artificial Neural Network (ANN) are seen to converge more slowly than the lower frequencies, is observed ubiquitously across ANNs. This has created technology challenges in fields where resolution of higher frequencies is crucial, like in Physics Informed Neural Networks (PINNs). Extre…
▽ More
The phenomena of Spectral Bias, where the higher frequency components of a function being learnt in a feedforward Artificial Neural Network (ANN) are seen to converge more slowly than the lower frequencies, is observed ubiquitously across ANNs. This has created technology challenges in fields where resolution of higher frequencies is crucial, like in Physics Informed Neural Networks (PINNs). Extreme Learning Machines (ELMs) that obviate an iterative solution process which provides the theoretical basis of Spectral Bias (SB), should in principle be free of the same. This work verifies the reliability of this assumption, and shows that it is incorrect. However, the structure of ELMs makes them naturally amenable to implementation of variants of Fourier Feature Embeddings, which have been shown to mitigate SB in ANNs. This approach is implemented and verified to completely eliminate SB, thus bringing into feasibility the application of ELMs for practical problems like PINNs where resolution of higher frequencies is essential.
△ Less
Submitted 19 July, 2023;
originally announced July 2023.
-
An adaptive approach to remove tensile instability in SPH for weakly compressible fluids
Authors:
Kanishka Bhattacharya,
Tapan Jana,
Amit Shaw,
L. S. Ramachandra,
Vishal Mehera
Abstract:
Smoothed Particle Hydrodynamics (SPH) is plagued by the phenomenon of tensile instability, which is the occurrence of short wavelength zero energy modes resulting in unphysical clustering of particles. The root cause of the instability is the shape of derivative of the compactly supported kernel function which may yield negative stiffness in the particle interaction under certain circumstances. In…
▽ More
Smoothed Particle Hydrodynamics (SPH) is plagued by the phenomenon of tensile instability, which is the occurrence of short wavelength zero energy modes resulting in unphysical clustering of particles. The root cause of the instability is the shape of derivative of the compactly supported kernel function which may yield negative stiffness in the particle interaction under certain circumstances. In this work, an adaptive algorithm is developed to remove tensile instability in SPH for weakly compressible fluids. Herein, a B-spline function is used as the SPH kernel and the knots of the B-spline are adapted to change the shape of the kernel, thereby satisfying the condition associated with stability. The knot-shifting criterion is based on the particle movement within the influence domain. This enables the prevention of instability in fluid problems where excessive rearrangement of particle positions occurs. A 1D dispersion analysis of an Oldroyd B fluid material model is performed to show how the algorithm prevents instabilities for short wavelengths but ensures accuracy at large wavelengths. The efficacy of the approach is demonstrated through a few benchmark fluid dynamics simulations where a visco-elastic Oldroyd B material model and a non-viscous Eulerian fluid material model are considered.
△ Less
Submitted 12 July, 2023;
originally announced July 2023.
-
Learning Homogenization for Elliptic Operators
Authors:
Kaushik Bhattacharya,
Nikola Kovachki,
Aakila Rajan,
Andrew M. Stuart,
Margaret Trautner
Abstract:
Multiscale partial differential equations (PDEs) arise in various applications, and several schemes have been developed to solve them efficiently. Homogenization theory is a powerful methodology that eliminates the small-scale dependence, resulting in simplified equations that are computationally tractable while accurately predicting the macroscopic response. In the field of continuum mechanics, h…
▽ More
Multiscale partial differential equations (PDEs) arise in various applications, and several schemes have been developed to solve them efficiently. Homogenization theory is a powerful methodology that eliminates the small-scale dependence, resulting in simplified equations that are computationally tractable while accurately predicting the macroscopic response. In the field of continuum mechanics, homogenization is crucial for deriving constitutive laws that incorporate microscale physics in order to formulate balance laws for the macroscopic quantities of interest. However, obtaining homogenized constitutive laws is often challenging as they do not in general have an analytic form and can exhibit phenomena not present on the microscale. In response, data-driven learning of the constitutive law has been proposed as appropriate for this task. However, a major challenge in data-driven learning approaches for this problem has remained unexplored: the impact of discontinuities and corner interfaces in the underlying material. These discontinuities in the coefficients affect the smoothness of the solutions of the underlying equations. Given the prevalence of discontinuous materials in continuum mechanics applications, it is important to address the challenge of learning in this context; in particular, to develop underpinning theory that establishes the reliability of data-driven methods in this scientific domain. The paper addresses this unexplored challenge by investigating the learnability of homogenized constitutive laws for elliptic operators in the presence of such complexities. Approximation theory is presented, and numerical experiments are performed which validate the theory in the context of learning the solution operator defined by the cell problem arising in homogenization for elliptic PDEs.
△ Less
Submitted 4 January, 2024; v1 submitted 21 June, 2023;
originally announced June 2023.
-
Modelling exposure between populations using networks of mobility during Covid-19
Authors:
Tuomas Takko,
Kunal Bhattacharya,
Kimmo Kaski
Abstract:
The use of mobile phone call detail records and device location data for the calling patterns, movements, and social contacts of individuals, has proven to be valuable for devising models and understanding of their mobility and behaviour patterns. In this study we investigate weighted exposure-networks of human daily activities in the capital region of Finland as a proxy for contacts between posta…
▽ More
The use of mobile phone call detail records and device location data for the calling patterns, movements, and social contacts of individuals, has proven to be valuable for devising models and understanding of their mobility and behaviour patterns. In this study we investigate weighted exposure-networks of human daily activities in the capital region of Finland as a proxy for contacts between postal code areas during the pre-pandemic year 2019 and pandemic years 2020, 2021 and early 2022. We investigate the suitability of gravity and radiation type models for reconstructing the exposure-networks based on geo-spatial and population mobility information. For this we use a mobile phone dataset of aggregated daily visits from a postal code area to cellphone grid locations, and treat it as a bipartite network to create weighted one mode projections using a weighted co-occurrence function. We fit a gravitation model and a radiation model to the averaged weekly and yearly projection networks with geo-spatial and socioeconomic variables of the postal code areas and their populations. We also consider an extended gravity type model comprising of additional postal area information such as distance via public transportation and population density. The results show that the co-occurrence of human activities, or exposure, between postal code areas follows both the gravity and radiation type interactions, once fitted to the empirical network. The effects of the pandemic beginning in 2020 can be observed as a decrease of the overall activity as well as of the exposure of the projected networks. In general, the results show that the postal code level networks changed to be more proximity weighted after the pandemic began, following the government imposed non-pharmaceutical interventions, with differences based on the geo-spatial and socioeconomic structure of the areas.
△ Less
Submitted 17 April, 2023; v1 submitted 9 January, 2023;
originally announced January 2023.
-
Investigations on convergence behaviour of Physics Informed Neural Networks across spectral ranges and derivative orders
Authors:
Mayank Deshpande,
Siddharth Agarwal,
Vukka Snigdha,
Arya Kumar Bhattacharya
Abstract:
An important inference from Neural Tangent Kernel (NTK) theory is the existence of spectral bias (SB), that is, low frequency components of the target function of a fully connected Artificial Neural Network (ANN) being learnt significantly faster than the higher frequencies during training. This is established for Mean Square Error (MSE) loss functions with very low learning rate parameters. Physi…
▽ More
An important inference from Neural Tangent Kernel (NTK) theory is the existence of spectral bias (SB), that is, low frequency components of the target function of a fully connected Artificial Neural Network (ANN) being learnt significantly faster than the higher frequencies during training. This is established for Mean Square Error (MSE) loss functions with very low learning rate parameters. Physics Informed Neural Networks (PINNs) are designed to learn the solutions of differential equations (DE) of arbitrary orders; in PINNs the loss functions are obtained as the residues of the conservative form of the DEs and represent the degree of dissatisfaction of the equations. So there has been an open question whether (a) PINNs also exhibit SB and (b) if so, how does this bias vary across the orders of the DEs. In this work, a series of numerical experiments are conducted on simple sinusoidal functions of varying frequencies, compositions and equation orders to investigate these issues. It is firmly established that under normalized conditions, PINNs do exhibit strong spectral bias, and this increases with the order of the differential equation.
△ Less
Submitted 7 January, 2023;
originally announced January 2023.
-
Knowledge mining of unstructured information: application to cyber-domain
Authors:
Tuomas Takko,
Kunal Bhattacharya,
Martti Lehto,
Pertti Jalasvirta,
Aapo Cederberg,
Kimmo Kaski
Abstract:
Information on cyber-related crimes, incidents, and conflicts is abundantly available in numerous open online sources. However, processing the large volumes and streams of data is a challenging task for the analysts and experts, and entails the need for newer methods and techniques. In this article we present and implement a novel knowledge graph and knowledge mining framework for extracting the r…
▽ More
Information on cyber-related crimes, incidents, and conflicts is abundantly available in numerous open online sources. However, processing the large volumes and streams of data is a challenging task for the analysts and experts, and entails the need for newer methods and techniques. In this article we present and implement a novel knowledge graph and knowledge mining framework for extracting the relevant information from free-form text about incidents in the cyberdomain. The framework includes a machine learning based pipeline for generating graphs of organizations, countries, industries, products and attackers with a non-technical cyber-ontology. The extracted knowledge graph is utilized to estimate the incidence of cyberattacks on a given graph configuration. We use publicly available collections of real cyber-incident reports to test the efficacy of our methods. The knowledge extraction is found to be sufficiently accurate, and the graph-based threat estimation demonstrates a level of correlation with the actual records of attacks. In practical use, an analyst utilizing the presented framework can infer additional information from the current cyber-landscape in terms of risk to various entities and propagation of the risk heuristic between industries and countries.
△ Less
Submitted 1 August, 2022; v1 submitted 8 September, 2021;
originally announced September 2021.
-
Neural Operator: Learning Maps Between Function Spaces
Authors:
Nikola Kovachki,
Zongyi Li,
Burigede Liu,
Kamyar Azizzadenesheli,
Kaushik Bhattacharya,
Andrew Stuart,
Anima Anandkumar
Abstract:
The classical development of neural networks has primarily focused on learning mappings between finite dimensional Euclidean spaces or finite sets. We propose a generalization of neural networks to learn operators, termed neural operators, that map between infinite dimensional function spaces. We formulate the neural operator as a composition of linear integral operators and nonlinear activation f…
▽ More
The classical development of neural networks has primarily focused on learning mappings between finite dimensional Euclidean spaces or finite sets. We propose a generalization of neural networks to learn operators, termed neural operators, that map between infinite dimensional function spaces. We formulate the neural operator as a composition of linear integral operators and nonlinear activation functions. We prove a universal approximation theorem for our proposed neural operator, showing that it can approximate any given nonlinear continuous operator. The proposed neural operators are also discretization-invariant, i.e., they share the same model parameters among different discretization of the underlying function spaces. Furthermore, we introduce four classes of efficient parameterization, viz., graph neural operators, multi-pole graph neural operators, low-rank neural operators, and Fourier neural operators. An important application for neural operators is learning surrogate maps for the solution operators of partial differential equations (PDEs). We consider standard PDEs such as the Burgers, Darcy subsurface flow, and the Navier-Stokes equations, and show that the proposed neural operators have superior performance compared to existing machine learning based methodologies, while being several orders of magnitude faster than conventional PDE solvers.
△ Less
Submitted 2 May, 2024; v1 submitted 18 August, 2021;
originally announced August 2021.
-
Learning Dissipative Dynamics in Chaotic Systems
Authors:
Zongyi Li,
Miguel Liu-Schiaffini,
Nikola Kovachki,
Burigede Liu,
Kamyar Azizzadenesheli,
Kaushik Bhattacharya,
Andrew Stuart,
Anima Anandkumar
Abstract:
Chaotic systems are notoriously challenging to predict because of their sensitivity to perturbations and errors due to time stepping. Despite this unpredictable behavior, for many dissipative systems the statistics of the long term trajectories are governed by an invariant measure supported on a set, known as the global attractor; for many problems this set is finite dimensional, even if the state…
▽ More
Chaotic systems are notoriously challenging to predict because of their sensitivity to perturbations and errors due to time stepping. Despite this unpredictable behavior, for many dissipative systems the statistics of the long term trajectories are governed by an invariant measure supported on a set, known as the global attractor; for many problems this set is finite dimensional, even if the state space is infinite dimensional. For Markovian systems, the statistical properties of long-term trajectories are uniquely determined by the solution operator that maps the evolution of the system over arbitrary positive time increments. In this work, we propose a machine learning framework to learn the underlying solution operator for dissipative chaotic systems, showing that the resulting learned operator accurately captures short-time trajectories and long-time statistical behavior. Using this framework, we are able to predict various statistics of the invariant measure for the turbulent Kolmogorov Flow dynamics with Reynolds numbers up to 5000.
△ Less
Submitted 27 September, 2022; v1 submitted 12 June, 2021;
originally announced June 2021.
-
Human-agent coordination in a group formation game
Authors:
Tuomas Takko,
Kunal Bhattacharya,
Daniel Monsivais,
Kimmo Kaski
Abstract:
Coordination and cooperation between humans and autonomous agents in cooperative games raises interesting questions of human decision making and behaviour changes. Here we report our findings from a group formation game in a small-world network of different mixes of human and agent players, aiming to achieve connected clusters of the same colour by swapping places with neighbouring players using n…
▽ More
Coordination and cooperation between humans and autonomous agents in cooperative games raises interesting questions of human decision making and behaviour changes. Here we report our findings from a group formation game in a small-world network of different mixes of human and agent players, aiming to achieve connected clusters of the same colour by swapping places with neighbouring players using non-overlapping information. In the experiments the human players are incentivized by rewarding to prioritize their own cluster while the model of agents' decision making is derived from our previous experiment of purely cooperative game between human players. The experiments were performed by grouping the players in three different setups to investigate the overall effect of having cooperative autonomous agents within teams. We observe that the change in the behavior of human subjects adjusts to playing with autonomous agents by being less risk averse, while keeping the overall performance efficient by splitting the behaviour into selfish and cooperative in the two actions performed during the rounds of the game. Moreover, results from two hybrid human-agent setups suggest that the group composition affects the evolution of clusters. Our findings indicate that in purely or lesser cooperative settings, providing more control to humans could help in maximizing the overall performance of hybrid systems.
△ Less
Submitted 20 May, 2021;
originally announced May 2021.
-
Fourier Neural Operator for Parametric Partial Differential Equations
Authors:
Zongyi Li,
Nikola Kovachki,
Kamyar Azizzadenesheli,
Burigede Liu,
Kaushik Bhattacharya,
Andrew Stuart,
Anima Anandkumar
Abstract:
The classical development of neural networks has primarily focused on learning mappings between finite-dimensional Euclidean spaces. Recently, this has been generalized to neural operators that learn mappings between function spaces. For partial differential equations (PDEs), neural operators directly learn the mapping from any functional parametric dependence to the solution. Thus, they learn an…
▽ More
The classical development of neural networks has primarily focused on learning mappings between finite-dimensional Euclidean spaces. Recently, this has been generalized to neural operators that learn mappings between function spaces. For partial differential equations (PDEs), neural operators directly learn the mapping from any functional parametric dependence to the solution. Thus, they learn an entire family of PDEs, in contrast to classical methods which solve one instance of the equation. In this work, we formulate a new neural operator by parameterizing the integral kernel directly in Fourier space, allowing for an expressive and efficient architecture. We perform experiments on Burgers' equation, Darcy flow, and Navier-Stokes equation. The Fourier neural operator is the first ML-based method to successfully model turbulent flows with zero-shot super-resolution. It is up to three orders of magnitude faster compared to traditional PDE solvers. Additionally, it achieves superior accuracy compared to previous learning-based solvers under fixed resolution.
△ Less
Submitted 16 May, 2021; v1 submitted 17 October, 2020;
originally announced October 2020.
-
Accelerated computational micromechanics
Authors:
Hao Zhou,
Kaushik Bhattacharya
Abstract:
We present an approach to solving problems in micromechanics that is amenable to massively parallel calculations through the use of graphical processing units and other accelerators. The problems lead to nonlinear differential equations that are typically second order in space and first order in time. This combination of nonlinearity and nonlocality makes such problems difficult to solve in parall…
▽ More
We present an approach to solving problems in micromechanics that is amenable to massively parallel calculations through the use of graphical processing units and other accelerators. The problems lead to nonlinear differential equations that are typically second order in space and first order in time. This combination of nonlinearity and nonlocality makes such problems difficult to solve in parallel. However, this combination is a result of collapsing nonlocal, but linear and universal physical laws (kinematic compatibility, balance laws), and nonlinear but local constitutive relations. We propose an operator-splitting scheme inspired by this structure. The governing equations are formulated as (incremental) variational problems, the differential constraints like compatibility are introduced using an augmented Lagrangian, and the resulting incremental variational principle is solved by the alternating direction method of multipliers. The resulting algorithm has a natural connection to physical principles, and also enables massively parallel implementation on structured grids. We present this method and use it to study two examples. The first concerns the long wavelength instability of finite elasticity, and allows us to verify the approach against previous numerical simulations. We also use this example to study convergence and parallel performance. The second example concerns microstructure evolution in liquid crystal elastomers and provides new insights into some counter-intuitive properties of these materials. We use this example to validate the model and the approach against experimental observations.
△ Less
Submitted 9 October, 2020;
originally announced October 2020.
-
Internal migration and mobile communication patterns among pairs with strong ties
Authors:
Mikaela Irene D. Fudolig,
Daniel Monsivais,
Kunal Bhattacharya,
Hang-Hyun Jo,
Kimmo Kaski
Abstract:
Using large-scale call detail records of anonymised mobile phone service subscribers with demographic and location information, we investigate how a long-distance residential move within the country affects the mobile communication patterns between an ego who moved and a frequently called alter who did not move. By using clustering methods in analysing the call frequency time series, we find that…
▽ More
Using large-scale call detail records of anonymised mobile phone service subscribers with demographic and location information, we investigate how a long-distance residential move within the country affects the mobile communication patterns between an ego who moved and a frequently called alter who did not move. By using clustering methods in analysing the call frequency time series, we find that such ego-alter pairs are grouped into two clusters, those with the call frequency increasing and those with the call frequency decreasing after the move of the ego. This indicates that such residential moves are correlated with a change in the communication pattern soon after moving. We find that the pre-move calling behaviour is a relevant predictor for the post-move calling behaviour. While demographic and location information can help in predicting whether the call frequency will rise or decay, they are not relevant in predicting the actual call frequency volume. We also note that at four months after the move, most of these close pairs maintain contact, even if the call frequency is decreased.
△ Less
Submitted 5 April, 2021; v1 submitted 1 September, 2020;
originally announced September 2020.
-
Multipole Graph Neural Operator for Parametric Partial Differential Equations
Authors:
Zongyi Li,
Nikola Kovachki,
Kamyar Azizzadenesheli,
Burigede Liu,
Kaushik Bhattacharya,
Andrew Stuart,
Anima Anandkumar
Abstract:
One of the main challenges in using deep learning-based methods for simulating physical systems and solving partial differential equations (PDEs) is formulating physics-based data in the desired structure for neural networks. Graph neural networks (GNNs) have gained popularity in this area since graphs offer a natural way of modeling particle interactions and provide a clear way of discretizing th…
▽ More
One of the main challenges in using deep learning-based methods for simulating physical systems and solving partial differential equations (PDEs) is formulating physics-based data in the desired structure for neural networks. Graph neural networks (GNNs) have gained popularity in this area since graphs offer a natural way of modeling particle interactions and provide a clear way of discretizing the continuum models. However, the graphs constructed for approximating such tasks usually ignore long-range interactions due to unfavorable scaling of the computational complexity with respect to the number of nodes. The errors due to these approximations scale with the discretization of the system, thereby not allowing for generalization under mesh-refinement. Inspired by the classical multipole methods, we propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Our multi-level formulation is equivalent to recursively adding inducing points to the kernel matrix, unifying GNNs with multi-resolution matrix factorization of the kernel. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
△ Less
Submitted 19 October, 2020; v1 submitted 16 June, 2020;
originally announced June 2020.
-
Model Reduction and Neural Networks for Parametric PDEs
Authors:
Kaushik Bhattacharya,
Bamdad Hosseini,
Nikola B. Kovachki,
Andrew M. Stuart
Abstract:
We develop a general framework for data-driven approximation of input-output maps between infinite-dimensional spaces. The proposed approach is motivated by the recent successes of neural networks and deep learning, in combination with ideas from model reduction. This combination results in a neural network approximation which, in principle, is defined on infinite-dimensional spaces and, in practi…
▽ More
We develop a general framework for data-driven approximation of input-output maps between infinite-dimensional spaces. The proposed approach is motivated by the recent successes of neural networks and deep learning, in combination with ideas from model reduction. This combination results in a neural network approximation which, in principle, is defined on infinite-dimensional spaces and, in practice, is robust to the dimension of finite-dimensional approximations of these spaces required for computation. For a class of input-output maps, and suitably chosen probability measures on the inputs, we prove convergence of the proposed approximation methodology. We also include numerical experiments which demonstrate the effectiveness of the method, showing convergence and robustness of the approximation scheme with respect to the size of the discretization, and compare it with existing algorithms from the literature; our examples include the mapping from coefficient to solution in a divergence form elliptic partial differential equation (PDE) problem, and the solution operator for viscous Burgers' equation.
△ Less
Submitted 17 June, 2021; v1 submitted 6 May, 2020;
originally announced May 2020.
-
Scaling the training of particle classification on simulated MicroBooNE events to multiple GPUs
Authors:
Alex Hagen,
Eric Church,
Jan Strube,
Kolahal Bhattacharya,
Vinay Amatya
Abstract:
Measurements in Liquid Argon Time Projection Chamber (LArTPC) neutrino detectors, such as the MicroBooNE detector at Fermilab, feature large, high fidelity event images. Deep learning techniques have been extremely successful in classification tasks of photographs, but their application to LArTPC event images is challenging, due to the large size of the events. Events in these detectors are typica…
▽ More
Measurements in Liquid Argon Time Projection Chamber (LArTPC) neutrino detectors, such as the MicroBooNE detector at Fermilab, feature large, high fidelity event images. Deep learning techniques have been extremely successful in classification tasks of photographs, but their application to LArTPC event images is challenging, due to the large size of the events. Events in these detectors are typically two orders of magnitude larger than images found in classical challenges, like recognition of handwritten digits contained in the MNIST database or object recognition in the ImageNet database. Ideally, training would occur on many instances of the entire event data, instead of many instances of cropped regions of interest from the event data. However, such efforts lead to extremely long training cycles, which slow down the exploration of new network architectures and hyperparameter scans to improve the classification performance. We present studies of scaling a LArTPC classification problem on multiple architectures, spanning multiple nodes. The studies are carried out on simulated events in the MicroBooNE detector. We emphasize that it is beyond the scope of this study to optimize networks or extract the physics from any results here. Institutional computing at Pacific Northwest National Laboratory and the SummitDev machine at Oak Ridge National Laboratory's Leadership Computing Facility have been used. To our knowledge, this is the first use of state-of-the-art Convolutional Neural Networks for particle physics and their attendant compute techniques onto the DOE Leadership Class Facilities. We expect benefits to accrue particularly to the Deep Underground Neutrino Experiment (DUNE) LArTPC program, the flagship US High Energy Physics (HEP) program for the coming decades.
△ Less
Submitted 17 April, 2020;
originally announced April 2020.
-
Neural Operator: Graph Kernel Network for Partial Differential Equations
Authors:
Zongyi Li,
Nikola Kovachki,
Kamyar Azizzadenesheli,
Burigede Liu,
Kaushik Bhattacharya,
Andrew Stuart,
Anima Anandkumar
Abstract:
The classical development of neural networks has been primarily for mappings between a finite-dimensional Euclidean space and a set of classes, or between two finite-dimensional Euclidean spaces. The purpose of this work is to generalize neural networks so that they can learn mappings between infinite-dimensional spaces (operators). The key innovation in our work is that a single set of network pa…
▽ More
The classical development of neural networks has been primarily for mappings between a finite-dimensional Euclidean space and a set of classes, or between two finite-dimensional Euclidean spaces. The purpose of this work is to generalize neural networks so that they can learn mappings between infinite-dimensional spaces (operators). The key innovation in our work is that a single set of network parameters, within a carefully designed network architecture, may be used to describe mappings between infinite-dimensional spaces and between different finite-dimensional approximations of those spaces. We formulate approximation of the infinite-dimensional mapping by composing nonlinear activation functions and a class of integral operators. The kernel integration is computed by message passing on graph networks. This approach has substantial practical consequences which we will illustrate in the context of mappings between input data to partial differential equations (PDEs) and their solutions. In this context, such learned networks can generalize among different approximation methods for the PDE (such as finite difference or finite element methods) and among approximations corresponding to different underlying levels of resolution and discretization. Experiments confirm that the proposed graph kernel network does have the desired properties and show competitive performance compared to the state of the art solvers.
△ Less
Submitted 6 March, 2020;
originally announced March 2020.
-
A stable SPH with adaptive B-spline kernel
Authors:
Saptarshi Kumar Lahiri,
Kanishka Bhattacharya,
Amit Shaw,
L S Ramachandra
Abstract:
Tensile instability, often observed in smoothed particle hydrodynamics (SPH), is a numerical artifact that manifests itself by unphysical clustering or separation of particles. The instability originates in estimating the derivatives of the smoothing functions which, when interact with material constitution may result in negative stiffness in the discretized system. In the present study, a stable…
▽ More
Tensile instability, often observed in smoothed particle hydrodynamics (SPH), is a numerical artifact that manifests itself by unphysical clustering or separation of particles. The instability originates in estimating the derivatives of the smoothing functions which, when interact with material constitution may result in negative stiffness in the discretized system. In the present study, a stable formulation of SPH is developed where the kernel function is continuously adapted at every material point depending on its state of stress. Bspline basis function with a variable intermediate knot is used as the kernel function. The shape of the kernel function is then modified by changing the intermediate knot position such that the condition associated with instability does not arise. While implementing the algorithm the simplicity and computational efficiency of SPH are not compromised. One-dimensional dispersion analysis is performed to understand the effect adaptive kernel on the stability. Finally, the efficacy of the algorithm is demonstrated through some benchmark elastic dynamics problems.
△ Less
Submitted 4 January, 2020;
originally announced January 2020.
-
Link-centric analysis of variation by demographics in mobile phone communication patterns
Authors:
Mikaela Irene D. Fudolig,
Kunal Bhattacharya,
Daniel Monsivais,
Hang-Hyun Jo,
Kimmo Kaski
Abstract:
We present a link-centric approach to study variation in the mobile phone communication patterns of individuals. Unlike most previous research on call detail records that focused on the variation of phone usage across individual users, we examine how the calling and texting patterns obtained from call detail records vary among pairs of users and how these patterns are affected by the nature of rel…
▽ More
We present a link-centric approach to study variation in the mobile phone communication patterns of individuals. Unlike most previous research on call detail records that focused on the variation of phone usage across individual users, we examine how the calling and texting patterns obtained from call detail records vary among pairs of users and how these patterns are affected by the nature of relationships between users. To demonstrate this link-centric perspective, we extract factors that contribute to the variation in the mobile phone communication patterns and predict demographics-related quantities for pairs of users. The time of day and the channel of communication (calls or texts) are found to explain most of the variance among pairs that frequently call each other. Furthermore, we find that this variation can be used to predict the relationship between the pairs of users, as inferred from their age and gender, as well as the age of the younger user in a pair. From the classifier performance across different age and gender groups as well as the inherent class overlap suggested by the estimate of the bounds of the Bayes error, we gain insights into the similarity and differences of communication patterns across different relationships.
△ Less
Submitted 16 December, 2019; v1 submitted 31 July, 2019;
originally announced July 2019.
-
Phase-field study of crack nucleation and propagation in elastic - perfectly plastic bodies
Authors:
Stella Brach,
Erwan Tanné,
Blaise Bourdin,
Kaushik Bhattacharya
Abstract:
Crack initiation and propagation in elastic - perfectly plastic bodies is studied in a phase-field or variational gradient damage formulation. A rate-independent formulation that naturally couples elasticity, perfect plasticity and fracture is presented, and used to study crack initiation in notched specimens and crack propagation using a surfing boundary condition. Both plane strain and plane str…
▽ More
Crack initiation and propagation in elastic - perfectly plastic bodies is studied in a phase-field or variational gradient damage formulation. A rate-independent formulation that naturally couples elasticity, perfect plasticity and fracture is presented, and used to study crack initiation in notched specimens and crack propagation using a surfing boundary condition. Both plane strain and plane stress are addressed. It is shown that in plane strain, a plastic zone blunts the notch or crack tip which in turn inhibits crack nucleation and propagation. Sufficient load causes the crack to nucleate or unpin, but the crack does so with a finite jump. Therefore the propagation is intermittent or jerky leaving behind a rough surface. In plane stress, failure proceeds with an intense shear zone ahead of the notch or crack tip and the fracture process is not complete.
△ Less
Submitted 12 December, 2018;
originally announced December 2018.
-
Different patterns of social closeness observed in mobile phone communication
Authors:
Mikaela Irene D. Fudolig,
Daniel Monsivais,
Kunal Bhattacharya,
Hang-Hyun Jo,
Kimmo Kaski
Abstract:
We analyze a large-scale mobile phone call dataset containing information on the age, gender, and billing locality of users to get insight into social closeness in pairs of individuals of similar age. We show that in addition to using the demographic information, the ranking of contacts by their call frequency in egocentric networks is crucial to characterize the different communication patterns.…
▽ More
We analyze a large-scale mobile phone call dataset containing information on the age, gender, and billing locality of users to get insight into social closeness in pairs of individuals of similar age. We show that in addition to using the demographic information, the ranking of contacts by their call frequency in egocentric networks is crucial to characterize the different communication patterns. We find that mutually top-ranked opposite-gender pairs show the highest levels of call frequency and daily regularity, which is consistent with the behavior of real-life romantic partners. At somewhat lower level of call frequency and daily regularity come the mutually top-ranked same-gender pairs, while the lowest call frequency and daily regularity are observed for mutually non-top-ranked pairs. We have also observed that older pairs tend to call less frequently and less regularly than younger pairs, while the average call durations exhibit a more complex dependence on age. We expect that a more detailed analysis can help us better characterize the nature of relationships between pairs of individuals and distinguish between various types of relations, such as siblings, friends, and romantic partners.
△ Less
Submitted 7 August, 2019; v1 submitted 30 August, 2018;
originally announced August 2018.
-
A Deep Neural Network for Pixel-Level Electromagnetic Particle Identification in the MicroBooNE Liquid Argon Time Projection Chamber
Authors:
MicroBooNE collaboration,
C. Adams,
M. Alrashed,
R. An,
J. Anthony,
J. Asaadi,
A. Ashkenazi,
M. Auger,
S. Balasubramanian,
B. Baller,
C. Barnes,
G. Barr,
M. Bass,
F. Bay,
A. Bhat,
K. Bhattacharya,
M. Bishai,
A. Blake,
T. Bolton,
L. Camilleri,
D. Caratelli,
I. Caro Terrazas,
R. Carr,
R. Castillo Fernandez,
F. Cavanna
, et al. (148 additional authors not shown)
Abstract:
We have developed a convolutional neural network (CNN) that can make a pixel-level prediction of objects in image data recorded by a liquid argon time projection chamber (LArTPC) for the first time. We describe the network design, training techniques, and software tools developed to train this network. The goal of this work is to develop a complete deep neural network based data reconstruction cha…
▽ More
We have developed a convolutional neural network (CNN) that can make a pixel-level prediction of objects in image data recorded by a liquid argon time projection chamber (LArTPC) for the first time. We describe the network design, training techniques, and software tools developed to train this network. The goal of this work is to develop a complete deep neural network based data reconstruction chain for the MicroBooNE detector. We show the first demonstration of a network's validity on real LArTPC data using MicroBooNE collection plane images. The demonstration is performed for stopping muon and a $ν_μ$ charged current neutral pion data samples.
△ Less
Submitted 22 August, 2018;
originally announced August 2018.
-
Social Physics: Uncovering Human Behaviour from Communication
Authors:
Kunal Bhattacharya,
Kimmo Kaski
Abstract:
In the post year 2000 era the technologies that facilitate human communication have rapidly multiplied. While the adoption of these technologies has hugely impacted the behaviour and sociality of people, specifically in urban but also in rural environments, their "digital footprints" on different data bases have become an active area of research. The existence and accessibility of such large popul…
▽ More
In the post year 2000 era the technologies that facilitate human communication have rapidly multiplied. While the adoption of these technologies has hugely impacted the behaviour and sociality of people, specifically in urban but also in rural environments, their "digital footprints" on different data bases have become an active area of research. The existence and accessibility of such large population-level datasets, has allowed scientists to study and model innate human tendencies and social patterns in an unprecedented way that complements traditional research approaches like questionnaire studies. In this review we focus on data analytics and modelling research - we call Social Physics - as it has been carried out using the mobile phone data sets to get insight into the various aspects of human sociality, burstiness in communication, mobility patterns, and daily rhythms.
△ Less
Submitted 13 April, 2018;
originally announced April 2018.
-
Group formation on a small-world: experiment and modelling
Authors:
Kunal Bhattacharya,
Tuomas Takko,
Daniel Monsivais,
Kimmo Kaski
Abstract:
As a step towards studying human-agent collectives we conduct an online game with human participants cooperating on a network. The game is presented in the context of achieving group formation through local coordination. The players set initially to a small world network with limited information on the location of other players, coordinate their movements to arrange themselves into groups. To unde…
▽ More
As a step towards studying human-agent collectives we conduct an online game with human participants cooperating on a network. The game is presented in the context of achieving group formation through local coordination. The players set initially to a small world network with limited information on the location of other players, coordinate their movements to arrange themselves into groups. To understand the decision making process we construct a data-driven model of agents based on probability matching. The model allows us to gather insight into the nature and degree of rationality employed by the human players. By varying the parameters in agent based simulations we are able to benchmark the human behaviour. We observe that while the players utilize the neighbourhood information in limited capacity, the perception of risk is optimal. We also find that for certain parameter ranges the agents are able to act more efficiently when compared to the human players. This approach would allow us to simulate the collective dynamics in games with agents having varying strategies playing alongside human proxies.
△ Less
Submitted 10 July, 2019; v1 submitted 2 March, 2018;
originally announced March 2018.
-
Peer relations with mobile phone data: Best friends and family formation
Authors:
Tamas David-Barrett,
Anna Rotkirch,
Asim Ghosh,
Kunal Bhattacharya,
Daniel Monsivais,
Isabel Behncke,
Janos Kertesz,
Kimmo Kaski
Abstract:
Earlier attempts to investigate the changes of the role of friendship in different life stages have failed due to lack of data. We close this gap by using a large data set of mobile phone calls from a European country in 2007, to study how the people's call patterns to their close social contacts are associated with age and gender of the callers. We hypothesize that (i) communication with peers, d…
▽ More
Earlier attempts to investigate the changes of the role of friendship in different life stages have failed due to lack of data. We close this gap by using a large data set of mobile phone calls from a European country in 2007, to study how the people's call patterns to their close social contacts are associated with age and gender of the callers. We hypothesize that (i) communication with peers, defined as callers of similar age, will be most important during the period of family formation and that (ii) the importance of best friends defined as same-sex callers of exactly the same age, will be stronger for women than for men. Results show that the frequency of phone calls with the same-sex peers in this population turns out to be relatively stable through life for both men and women. In line with the first hypothesis, there was a significant increase in the length of the phone calls for callers between ages 30 to 40 years. Partly in line with the second hypothesis, the increase in phone calls turned out to be particularly pronounced among females, although there were only minor gender differences in call frequencies. Furthermore, women tended to have long phone conversations with their same-age female friend, and also with somewhat older peers. In sum, we provide evidence from big data for the adult life stages at which peers are most important, and suggest that best friends appear to have a niche of their own in human sociality.
△ Less
Submitted 25 August, 2017;
originally announced August 2017.
-
Quantifying gender preferences across humans lifespan
Authors:
Asim Ghosh,
Daniel Monsivais,
Kunal Bhattacharya,
Robin I. M. Dunbar,
Kimmo Kaski
Abstract:
In human relations individuals' gender and age play a key role in the structures and dynamics of their social arrangements. In order to analyze the gender preferences of individuals in interaction with others at different stages of their lives we study a large mobile phone dataset. To do this we consider four fundamental gender-related caller and callee combinations of human interactions, namely m…
▽ More
In human relations individuals' gender and age play a key role in the structures and dynamics of their social arrangements. In order to analyze the gender preferences of individuals in interaction with others at different stages of their lives we study a large mobile phone dataset. To do this we consider four fundamental gender-related caller and callee combinations of human interactions, namely male to male, male to female, female to male, and female to female, which together with age, kinship, and different levels of friendship give rise to a wide scope of human sociality. Here we analyse the relative strength of these four types of interaction using a large dataset of mobile phone communication records. Our analysis suggests strong age dependence for an ego of one gender choosing to call an individual of either gender. We observe a strong opposite sex bonding across most of their reproductive age. However, older women show a strong tendency to connect to another female that is one generation younger in a way that is suggestive of the \emph{grandmothering effect}. We also find that the relative strength among the four possible interactions depends on phone call duration. For calls of medium and long duration, opposite gender interactions are significantly more probable than same gender interactions during the reproductive years, suggesting potential emotional exchange between spouses. By measuring the fraction of calls to other generations we find that mothers tend to make calls more to their daughters than to their sons, whereas fathers make calls more to their sons than to their daughters. For younger people, most of their calls go to same generation alters, while older people call the younger people more frequently, which supports the suggestion that \emph{affection flows downward}.
△ Less
Submitted 18 November, 2016;
originally announced November 2016.
-
Absence makes the heart grow fonder: social compensation when failure to interact risks weakening a relationship
Authors:
Kunal Bhattacharya,
Asim Ghosh,
Daniel Monsivais,
Robin Dunbar,
Kimmo Kaski
Abstract:
Social networks require active relationship maintenance if they are to be kept at a constant level of emotional closeness. For primates, including humans, failure to interact leads inexorably to a decline in relationship quality, and a consequent loss of the benefits that derive from individual relationships. As a result, many social species compensate for weakened relationships by investing more…
▽ More
Social networks require active relationship maintenance if they are to be kept at a constant level of emotional closeness. For primates, including humans, failure to interact leads inexorably to a decline in relationship quality, and a consequent loss of the benefits that derive from individual relationships. As a result, many social species compensate for weakened relationships by investing more heavily in them. Here we study how humans behave in similar situations, using data from mobile call detail records from a European country. For the less frequent contacts between pairs of communicating individuals we observe a logarithmic dependence of the duration of the succeeding call on the time gap with the previous call. We find that such behaviour is likely when the individuals in these dyadic pairs have the same gender and are in the same age bracket as well as being geographically distant. Our results indicate that these pairs deliberately invest more time in communication so as to reinforce their social bonding and prevent their relationships decaying when these are threatened by lack of interaction.
△ Less
Submitted 5 August, 2016;
originally announced August 2016.
-
Seasonal and geographical impact on human resting periods
Authors:
Daniel Monsivais,
Kunal Bhattacharya,
Asim Ghosh,
Robin I. M. Dunbar,
Kimmo Kaski
Abstract:
We study the influence of seasonally and geographically related daily dynamics of daylight and ambient temperature on human resting or sleeping patterns using mobile phone data of a large number of individuals. We observe two daily inactivity periods in the people's aggregated mobile phone calling patterns and infer these to represent the resting times of the population. We find that the nocturnal…
▽ More
We study the influence of seasonally and geographically related daily dynamics of daylight and ambient temperature on human resting or sleeping patterns using mobile phone data of a large number of individuals. We observe two daily inactivity periods in the people's aggregated mobile phone calling patterns and infer these to represent the resting times of the population. We find that the nocturnal resting period is strongly influenced by the length of daylight, and that its seasonal variation depends on the latitude, such that for people living in two different cities separated by eight latitudinal degrees, the difference in the resting period of people between the summer and winter in southern cities is almost twice that in the northern cities. We also observe that the duration of the afternoon resting period is influenced by the temperature, and that there is a threshold from which this influence sets in. Finally, we observe that the yearly dynamics of the afternoon and nocturnal resting periods appear to be counterbalancing each other. This also lends support to the notion that the total daily resting time of people is more or less conserved across the year.
△ Less
Submitted 20 April, 2017; v1 submitted 21 July, 2016;
originally announced July 2016.
-
Communication with family and friends across the life course
Authors:
Tamas David-Barrett,
Janos Kertesz,
Anna Rotkirch,
Asim Ghosh,
Kunal Bhattacharya,
Daniel Monsivais,
Kimmo Kaski
Abstract:
Each stage of the human life course is characterized by a distinctive pattern of social relations. We study how the intensity and importance of the closest social contacts vary across the life course, using a large database of mobile communication from a European country. We first determine the most likely social relationship type from these mobile phone records by relating the age and gender of t…
▽ More
Each stage of the human life course is characterized by a distinctive pattern of social relations. We study how the intensity and importance of the closest social contacts vary across the life course, using a large database of mobile communication from a European country. We first determine the most likely social relationship type from these mobile phone records by relating the age and gender of the caller and recipient to the frequency, length, and direction of calls. We then show how communication patterns between parents and children, romantic partner, and friends vary across the six main stages of the adult family life course. Young adulthood is dominated by a gradual shift of call activity from parents to close friends, and then to a romantic partner, culminating in the period of early family formation during which the focus is on the romantic partner. During middle adulthood call patterns suggest a high dependence on the parents of the ego, who, presumably often provide alloparental care, while at this stage female same-gender friendship also peaks. During post-reproductive adulthood, individuals and especially women balance close social contacts among three generations. The age of grandparenthood brings the children entering adulthood and family formation into the focus, and is associated with a realignment of close social contacts especially among women, while the old age is dominated by dependence on their children.
△ Less
Submitted 30 December, 2015;
originally announced December 2015.
-
Sex differences in social focus across the lifecycle in humans
Authors:
Kunal Bhattacharya,
Asim Ghosh,
Daniel Monsivais,
Robin I. M. Dunbar,
Kimmo Kaski
Abstract:
Age and gender are two important factors that play crucial roles in the way organisms allocate their social effort. In this study, we analyse a large mobile phone dataset to explore the way lifehistory influences human sociality and the way social networks are structured. Our results indicate that these aspects of human behaviour are strongly related to the age and gender such that younger individ…
▽ More
Age and gender are two important factors that play crucial roles in the way organisms allocate their social effort. In this study, we analyse a large mobile phone dataset to explore the way lifehistory influences human sociality and the way social networks are structured. Our results indicate that these aspects of human behaviour are strongly related to the age and gender such that younger individuals have more contacts and, among them, males more than females. However, the rate of decrease in the number of contacts with age differs between males and females, such that there is a reversal in the number of contacts around the late 30s. We suggest that this pattern can be attributed to the difference in reproductive investments that are made by the two sexes. We analyse the inequality in social investment patterns and suggest that the age and gender-related differences that we find reflect the constraints imposed by reproduction in a context where time (a form of social capital) is limited.
△ Less
Submitted 27 August, 2015;
originally announced August 2015.
-
Facility location problems in the constant work-space read-only memory model
Authors:
Binay K. Bhattacharya,
Minati De,
Subhas C. Nandy,
Sasanka Roy
Abstract:
Facility location problems are captivating both from theoretical and practical point of view. In this paper, we study some fundamental facility location problems from the space-efficient perspective. Here the input is considered to be given in a read-only memory and only constant amount of work-space is available during the computation. This {\em constant-work-space model} is well-motivated for ha…
▽ More
Facility location problems are captivating both from theoretical and practical point of view. In this paper, we study some fundamental facility location problems from the space-efficient perspective. Here the input is considered to be given in a read-only memory and only constant amount of work-space is available during the computation. This {\em constant-work-space model} is well-motivated for handling big-data as well as for computing in smart portable devices with small amount of extra-space.
First, we propose a strategy to implement prune-and-search in this model. As a warm up, we illustrate this technique for finding the Euclidean 1-center constrained on a line for a set of points in $\IR^2$. This method works even if the input is given in a sequential access read-only memory. Using this we show how to compute (i) the Euclidean 1-center of a set of points in $\IR^2$, and (ii) the weighted 1-center and weighted 2-center of a tree network. The running time of all these algorithms are $O(n~poly(\log n))$. While the result of (i) gives a positive answer to an open question asked by Asano, Mulzer, Rote and Wang in 2011, the technique used can be applied to other problems which admit solutions by prune-and-search paradigm. For example, we can apply the technique to solve two and three dimensional linear programming in $O(n~poly(\log n))$ time in this model. To the best of our knowledge, these are the first sub-quadratic time algorithms for all the above mentioned problems in the constant-work-space model. We also present optimal linear time algorithms for finding the centroid and weighted median of a tree in this model.
△ Less
Submitted 14 September, 2014;
originally announced September 2014.