{"entities":{"Q5941086":{"pageid":8117888,"ns":120,"title":"Item:Q5941086","lastrevid":102072875,"modified":"2026-06-06T03:25:33Z","type":"item","id":"Q5941086","labels":{"en":{"language":"en","value":"A cost optimal parallel algorithm for computing force field in \\(N-\\)body simulations on a CREW PRAM"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1635251"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$6BDF12CC-7153-45C1-B605-A2AD0BA6A394","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"440c13f89571300377d840962db818eba98b1d2d","datavalue":{"value":{"text":"A cost optimal parallel algorithm for computing force field in \\(N-\\)body simulations on a CREW PRAM","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5941086$F1A71E1D-5118-4789-AF15-5F506507CCF2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d708dabb6eba67538458af0299ff78218db8c7c3","datavalue":{"value":"0974.68244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941086$4E76A2B6-7BB2-4E7F-9DA8-BCAB50685BCC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"06c040fda45db507d16f33073a955df3f5867259","datavalue":{"value":"10.1016/S0304-3975(99)00326-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941086$F6497FFD-6EAD-48AB-B31D-91FDF7AEB948","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0391b7c4dfba8c377da7d81f897d3cf43a7a75ee","datavalue":{"value":{"entity-type":"item","numeric-id":166207,"id":"Q166207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$8B98C4F4-2DBE-4C4A-87F1-BBA26AA8EC91","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$1DDEF120-2D71-42EE-8A92-FD58688D668C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d780905acb67c2b1b938af03e08b68df411214b","datavalue":{"value":{"time":"+2001-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5941086$9C41A7C5-E734-4B45-8B1E-3B63CD8E16A8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8de44a09b00dab1f7b924aef5548ec410fc30850","datavalue":{"value":"We consider the following force field computation problem: given a cluster of \\(n\\) particles in three-dimensional space, compute the force exerted on each particle by the other particles. Depending on different applications, the pairwise interaction could be either gravitational or Lennard-Jones. In both cases, the force between two particles vanishes as the distance between them approaches to infinity. Since there are \\(n(n-1)/2\\) pairs, direct method requires \\(\\Theta(n^{2})\\) time for force evaluation, which is very expensive for astronomical simulations. In 1985 and 1986, two famous \\(\\Theta(n\\log n)\\) time hierarchical tree algorithms were published by \\textit{A. W. Appel} [SIAM J. Sci. Statist. Comput. 6, 85-103 (1985)] and by \\textit{J. Barnes} and \\textit{P. Hut} [Nature 324, 446-449 (1980)], respectively. In a recent paper, we presented a linear time algorithm which builds the oct tree bottom-up and showed that Appel's algorithm can be implemented in \\(\\Theta(n)\\) sequential time. In this paper, we present an algorithm which computes the force field in \\(\\Theta(\\log n)\\) time on a \\(\\Theta(n\\log n)\\) processor CREW PRAM. A key to this optimal parallel algorithm is replacing a recursive top-down force calculation procedure of Appel by an equivalent non-recursive bottom-up procedure. Our parallel algorithm also yields a new \\(\\Theta(n)\\) time-sequential algorithm for force field computation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941086$E80844DE-70A5-45D9-B8AD-87E926454CE4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941086$B92D6BB1-994E-47DD-A240-8F9AAEDBAB15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0e40b847cfa456e95c1c964a8cd9df72656b7c29","datavalue":{"value":"68U20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941086$098BFF2F-0F1E-4594-98E7-DEC4C77D29FE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e8aee90ae49ebff0994c28a9e4b6aa6c20c112bb","datavalue":{"value":"1635251","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5941086$8C296D6B-110B-4EA9-AF62-83903AC9C528","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d29423b09628a439a6adbfd4d66f545cfc48802f","datavalue":{"value":"spatial tree algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941086$05028126-9459-471A-8C64-2C6A9219575E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bae4e046802f4107ec64876fc72c319c50573a6","datavalue":{"value":"force field evaluation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941086$31B93E43-B086-4AA5-A258-486BD5BB4706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0d4dd51e18435c6e5b73fee7a7e59ca7db57ae7","datavalue":{"value":"body simulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941086$09B1B32E-7781-4504-88F4-FD85749F6621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f90139540a7d903d3d1c4be37d3cee7145f7063","datavalue":{"value":"PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941086$CA22C368-FA88-44DE-A497-CBC5418906F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cb8ee6bf446863dd9cb13814c2e30a68fd126e6","datavalue":{"value":"cost optimal algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5941086$2CD848CC-7C0B-4E23-86D2-E6217E0D44FC","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$5799901C-E971-420F-A1A0-C61FF0B23B8E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c6f1a2446b174ecdb3de974388c7c1d188fcdf","datavalue":{"value":{"entity-type":"item","numeric-id":4883671,"id":"Q4883671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$9229D9CC-E553-4923-BA48-D37AA418AA5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"440ba0d9dbee427a1b508f6b771488e2dd84f87d","datavalue":{"value":{"entity-type":"item","numeric-id":4369857,"id":"Q4369857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$8400B2EE-D92E-4659-9C9A-07BAD3E508BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"645ee79c043b86686d33996b7d338521ea74c2b6","datavalue":{"value":{"entity-type":"item","numeric-id":1186593,"id":"Q1186593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$4EEBF6C6-28CF-4175-A4DE-0E8A35FFA403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ca22f2a3f78ede1951e06155a4d7bd1585f820f","datavalue":{"value":{"entity-type":"item","numeric-id":1274364,"id":"Q1274364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$242904D1-54DB-4EBE-9603-5D8FD3BD853A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bd07bc09dedd761e445d59a50fbc70d9fc3bbe8","datavalue":{"value":{"entity-type":"item","numeric-id":5903478,"id":"Q5903478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$96AD9D17-88C3-4404-9502-716CF303965D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0bb09116c62e126468a72500019ab9ab3f8e9e9","datavalue":{"value":{"entity-type":"item","numeric-id":3811780,"id":"Q3811780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$AFB13344-6795-4C45-B546-560AD2BBE0FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48ed10f66b8516f117e22d01ccf2f2a8a2737dcb","datavalue":{"value":{"entity-type":"item","numeric-id":3101338,"id":"Q3101338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$6D3878E6-5189-4551-9437-A3F1B6AE6DE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99a4c571abde364490f8a25bf7bf648673904a30","datavalue":{"value":{"entity-type":"item","numeric-id":4864234,"id":"Q4864234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$FD96B642-7F0E-4348-8ED9-1137744A1570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28779ef8f7df1c1f4af61bc38a325816e0ec5b5f","datavalue":{"value":{"entity-type":"item","numeric-id":1898222,"id":"Q1898222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$3141B94B-309E-4D83-B5CA-C04C1377BAA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fb8496aff6a9a05ddf5f548e4b2602bbed2bd6c","datavalue":{"value":{"entity-type":"item","numeric-id":1374373,"id":"Q1374373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$62E1B70C-E9E2-445B-8951-A19EE2AEB75E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da30fe0ccf95ad338e64e96a46b9488b5ebb8b46","datavalue":{"value":{"entity-type":"item","numeric-id":1128668,"id":"Q1128668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$1B48EBFD-80A4-4354-8EB1-392BA00F90F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dbe0af9694d6a512fc5e3d13508715b8a298900","datavalue":{"value":{"entity-type":"item","numeric-id":3358273,"id":"Q3358273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5941086$6F593366-2AB9-4B3E-9900-4159CDE37411","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3b23d9002aa8d6b2f45c5f07a459873f805675f","datavalue":{"value":{"entity-type":"item","numeric-id":4218411,"id":"Q4218411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99fa67aac0225720635eb28c0891d264d4cd977e","datavalue":{"value":{"amount":"+0.9916113615036012","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941086$14C545BA-E68B-4B7B-8021-7ACAFFDCDAF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86cda054ee1e2934259b8bd06e3e20b771567834","datavalue":{"value":{"entity-type":"item","numeric-id":1339959,"id":"Q1339959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99fa67aac0225720635eb28c0891d264d4cd977e","datavalue":{"value":{"amount":"+0.9916113615036012","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941086$3BBE734E-CB08-4807-8B2D-3EA86AC859F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05d34bafd0b0df6b39c8848cc8bede42de14a53a","datavalue":{"value":{"entity-type":"item","numeric-id":1128668,"id":"Q1128668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48b0e2cd4a01c083792b15d3ded88e17a67328cb","datavalue":{"value":{"amount":"+0.904550075531006","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941086$1C6E1C16-582E-4CA5-B873-DC40DB675656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b48da8d28476bd3eb62fa9324100c2a69ac9ff6e","datavalue":{"value":{"entity-type":"item","numeric-id":4860168,"id":"Q4860168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e46b368910095c431327dbe55caedba00665fd85","datavalue":{"value":{"amount":"+0.9041723012924194","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941086$F12F871A-7416-408F-AB72-1FB159735450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc2cb7b73af7d61c2e9dc0e41e4217995e4c01f1","datavalue":{"value":{"entity-type":"item","numeric-id":3833682,"id":"Q3833682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf19017ee887a61c6dfce12e3fd623ae484edeb5","datavalue":{"value":{"amount":"+0.8200013637542725","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5941086$CE21070A-2333-48DC-AB7F-08A85BAA1CCA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A cost optimal parallel algorithm for computing force field in \\(N-\\)body simulations on a CREW PRAM","badges":[]}}}}}