🚀 go-pugleaf

On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:
> Być może nawet gdy się równa, to może być nieopłacalne, gdy n będzie 
> równe np. milion, wtedy x^n będzie wolniejsze dla początkowych danych 
> niż 2^x.
> 
> Ale..
> 
> "
> Toshiba stworzyła algorytm, który ma wyprzedzać komputery kwantowe
> oshiba twierdzi, że udało im się stworzyć algorytm, który wyprzedza 
> komputery kwantowe przy wykorzystaniu standardowego hardware’u. Firma ma 
> zamiar skomercjalizować swoje rozwiązanie.
> 
> Przed rynkiem komputerowym stoi ogromne wyzwanie. Powoli zbliżamy się do 
> kresu możliwości tradycyjnego krzemu. Wkrótce (jest to prawdopodobnie 
> kwestia kilku lat) zwiększenie wydajność PC-tów będzie ogromnym 
> wyzwaniem. Tymczasem na świecie jest coraz więcej danych, które trzeba 
> przetwarzać i analizować. Komputery radzą sobie z tym coraz gorzej i 
> stąd duża wiara w komputery kwantowe, które miałyby rozwiązać wiele 
> dzisiejszych problemów. Tymczasem Toshiba twierdzi, że znalazła inny sposób.
> 
> Japońska firma od kilku lat miała pracować i doskonalić algorytm do 
> przetwarzania i analizowania dużych ilości danych. SBA (Simulated 
> Bifurcation Algorithm) w końcu jest gotowy i efekty są ponoć bardzo 
> zaskakujące. Zdaniem przedstawicieli Toshiby radzi on sobie lepiej niż 
> rozwiązania stosowane w najszybszych superkomputerach, a nawet 
> komputerach kwantowych. W trakcie demonstracji pokazano, jak algorytm 
> znajduje się rozwiązanie dla problemu z 2000 połączonych zmiennych w 
> zaledwie 50 mikrosekund. To mniej więcej 10 raczy szybciej niż oparte na 
> laserach komputery kwantowe.
> 
> Chociaż nad komputerami kwantowymi pracują największe firmy 
> technologiczne na świecie, to wciąż efekty nie zadowalają. Powstały już 
> co prawda pierwsze urządzenia, ale są one bardzo ograniczone i pod 
> względem wydajności daleko im do tego, co byłoby wymagane w praktyce. 
> Dlatego algorytm Toshiby może być pewnego rodzaju rewolucją. Czas 
> pokaże, co z tego wyjdzie.
> "
> https://gamingsociety.pl/artykul/toshiba-simulated-bifurcation-algorithm-1099121/

Tyle znalazłem na wiki:

https://pl.wikipedia.org/wiki/Bifurkacja_(matematyka)

Gdzie można coś więcej doczytać na temat samej teorii?

Pozdrawiam

On 1/22/20 2:21 AM, M.M. wrote:
> Gdzie można coś więcej doczytać na temat samej teorii?

Fraktale i chaos, choćby książka którą kupiłem jeszcze na studiach:

Fraktale i chaos (ta mała książka) - Jacek Kudrewicz
Fraktale. Granice chaosu (Ta duża ksiażka)- H.-O.Peitgen, H.Jurgens, 
D.Saupe (rok 1995)


Ciekawe, może teoria bifurkacji była by przydatna do utrzymywania plazmy 
w Tokamaku? A ostatnio z Chin były wiadomości o sukcesach...

On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:
> Być może nawet gdy się równa, to może być nieopłacalne, gdy n będzie 
> równe np. milion, wtedy x^n będzie wolniejsze dla początkowych danych 
> niż 2^x.
> 
> Ale..
> 
> "
> Toshiba stworzyła algorytm, który ma wyprzedzać komputery kwantowe
> oshiba twierdzi, że udało im się stworzyć algorytm, który wyprzedza 
> komputery kwantowe przy wykorzystaniu standardowego hardware’u. Firma ma 
> zamiar skomercjalizować swoje rozwiązanie.
> 
> Przed rynkiem komputerowym stoi ogromne wyzwanie. Powoli zbliżamy się do 
> kresu możliwości tradycyjnego krzemu. Wkrótce (jest to prawdopodobnie 
> kwestia kilku lat) zwiększenie wydajność PC-tów będzie ogromnym 
> wyzwaniem. Tymczasem na świecie jest coraz więcej danych, które trzeba 
> przetwarzać i analizować. Komputery radzą sobie z tym coraz gorzej i 
> stąd duża wiara w komputery kwantowe, które miałyby rozwiązać wiele 
> dzisiejszych problemów. Tymczasem Toshiba twierdzi, że znalazła inny sposób.
> 
> Japońska firma od kilku lat miała pracować i doskonalić algorytm do 
> przetwarzania i analizowania dużych ilości danych. SBA (Simulated 
> Bifurcation Algorithm) w końcu jest gotowy i efekty są ponoć bardzo 
> zaskakujące. Zdaniem przedstawicieli Toshiby radzi on sobie lepiej niż 
> rozwiązania stosowane w najszybszych superkomputerach, a nawet 
> komputerach kwantowych. W trakcie demonstracji pokazano, jak algorytm 
> znajduje się rozwiązanie dla problemu z 2000 połączonych zmiennych w 
> zaledwie 50 mikrosekund. To mniej więcej 10 raczy szybciej niż oparte na 
> laserach komputery kwantowe.
> 
> Chociaż nad komputerami kwantowymi pracują największe firmy 
> technologiczne na świecie, to wciąż efekty nie zadowalają. Powstały już 
> co prawda pierwsze urządzenia, ale są one bardzo ograniczone i pod 
> względem wydajności daleko im do tego, co byłoby wymagane w praktyce. 
> Dlatego algorytm Toshiby może być pewnego rodzaju rewolucją. Czas 
> pokaże, co z tego wyjdzie.
> "
> https://gamingsociety.pl/artykul/toshiba-simulated-bifurcation-algorithm-1099121/

https://phys.org/news/2019-04-toshiba-breakthrough-algorithm-world-fastest.html

"Toshiba has solved these issues by developing a novel combinatorial optimization algorithm, the Simulated Bifurcation Algorithm. It is highly parallelizable, and can therefore easily speed up problem solving on standard digital computer through parallel computation. As current large-scale computational systems can be used as is, there is no need to install new equipment, making it easy to scale up at a low cost."

w.

On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:

> Ale..

Żade ale. To nie ma nic wsplnego z N ?= NP.
To algorytm probabilistyczny, przybliżony, aproksymacyjny... 
Komiwojadzera też mozęsz rozwiązać w czasie liniowym, tylko niedokładnie.
pytanie czy P=NP dotyczy znajdowania ścisłego, optymalnego rozwiązania. 
Ale dla wielu rzeczywistych przpadków takie przybliżone
rozwiązanie jest wystarczająco dobre. 

I tu zaproponowali takie przylizone rozwiązanie*) dla jakeigoś
problemu kombinarytorycznego, coś z modelem Isinga. 

https://www.researchgate.net/publication/332535366_Combinatorial_optimization_by_simulating_adiabatic_bifurcations_in_nonlinear_Hamiltonian_systems

Porównują się do symulowanego wyzarzania i jakeigoś algorytmu 
zaprojektowanego pos isinga. 

*) kantowy w sumie daje to samo:)


pzdr
bartekltg

Borneq <borneq@antyspam.hidden.pl> Wrote in message:
> On 1/22/20 2:21 AM, M.M. wrote:> Gdzie można coś więcej doczytać na temat samej teorii?Fraktale i chaos, choćby książka którą kupiłem jeszcze na studiach:Fraktale i chaos (ta mała książka) - Jacek KudrewiczFraktale. Granice chaosu (Ta duża ksiażka)- H.-O.Peitgen, H.Jurgens, D.Saupe (rok 1995)Ciekawe, może teoria bifurkacji była by przydatna do utrzymywania plazmy w Tokamaku? A ostatnio z Chin były wiadomości o sukcesach...


Ajtam, to działa w drugą stronę - ponieważ jest chaos --->
 tokamaki są niepewne w działaniu ---> w parę mikrosekund
 zniszczone będą elementy których wymiana trwa pół roku i kosztuje
 gigaeuro. Teoria chaosu ładnie i grzecznie tłumaczy dlaczego nie
 da się tego przeskoczyć. Konkretnie - dlaczego metody numeryczne
 (r.r. cząstkowe dynamiki plazmy) są nieskuteczne. Jedyne co można
 - utrzymać tokamak (ew. stellarator) poza chaosem - czyli w
 obszarze kiedy niby się jeszcze ma kontrolę. Patrz "wykładnik
 Łapunowa".

Nota bene: nie ma consensusu co do tego jakie równania napisać...
 Można wybierać z około 20 - coś tam sobie wziąć, a coś
 pominąć.

Potem kwestia jak rozwiązywać - jak się uprzeć 10 lat na
 superkomputerze dla jednej konfiguracji parametrów. Więc szuka
 się oszczędności - optymalizuje algorytmy. A to oznacza
 uproszczenia modelu - więc być może błędne wywalanie istotnych
 rzeczy.

-- 


----Android NewsGroup Reader----
http://usenet.sinaapp.com/

On Wednesday, January 22, 2020 at 6:02:12 PM UTC+1, bartekltg wrote:
> On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:
> 
> > Ale..
> 
> Żade ale. To nie ma nic wsplnego z N ?= NP.
> To algorytm probabilistyczny, przybliżony, aproksymacyjny... 

Chyba że w innym sensie niż klasycznym... Ale nie piszą też nic o tym, że
ich algorytm jest aproksymacyjny.

[
These problemsare NOTORIOUSLY DIFFICULT because of combinatorial explosion (1,2). Thus,special-purpose hardware devices for these problems are expected to beuseful. In particular, “Ising machines”designed for finding a groundstate of the Ising spin model (3) have recently attracted much attentionbecause many combinatorial optimization problems CAN BE MAPPED tothe Ising problem (4), including very-large-scale integrated circuit de-sign (5), drug design (6), and financial portfolio management (7). Thesemachines have been developed by various approaches: quantum com-puters based on quantum annealing (8,9) or quantum adiabatic opti-mization (10–12) implemented with superconducting circuits (13,14),coherent Ising machines (CIMs) implemented with laser pulses (15–20),and Ising machines based on simulated annealing (SA) (1,21,22)im-plemented with digital circuits such as field-programmable gate arrays(FPGAs) (23–29).
]


[
In this challenge, intense research efforts are underway to pave alternative approaches for computing and information processing. Among them, Ising machines have been shown to offer viable solutions for important NP-hard problems such as MAX-CUT 6 , protein folding 7 , and traveling salesman 8 , among others [9][10][11][12][13][14][15] . To this end, a variety of Ising machines have been demonstrated in effective spin systems of trapped atoms 16,17 , polariton condensates 18 , superconducting circuits 19 , coupled oscillators [20][21][22] , nanophotonic waveguides [23][24][25] , randomly coupled lasers [26][27][28] , and time-multiplexed optical parametric oscillators 29,30 
]

Klasycznie/asymptotycznie też nie wierzę żeby NP=P na dowolnym rozmiarze, w
łatwiej postawione wyzwania też nie dowierzam. Ale można szukać bardzo
szybkich i w miarę dokładnych algorytmów dla problemów o ograniczonym rozmiarze.

Tu też ciekawszy cytat:
[
Solving an all-to-all connected 2000-node MAX-CUTproblem by a single-FPGA SB machineFrom the advantages and properties of SB, we expect that SB will beuseful for approximately solving large-scale Ising or MAX-CUT prob-lems with dense connectivity as fast as possible. To check this expec-tation, we compare our SB machine with a state-of-the-art CIM (17,19),because this machine has achieved outstanding performance for theseproblems. For this comparison, we solved an all-to-all connected 2000-node MAX-CUT problem named K2000,whichwassolvedbytheCIM(17,19).We implemented an SB-based 2000-spin Ising machine with a singleFPGA. The product-sum operation, ∑Nj¼1Ji;jxj, in Eq. 8, which is the mostcomputation-intensive part in SB, is performed efficiently by massivelyparallel processing. Ji,jxjterms of up to 8192 are processed at a singleclock, which is about four times more than the total spins. See the Sup-plementary Materials for details.One of the main results in (17) is that the CIM reached a targetenergy given by the Goemans-Williamson semidefinite programming(GW-SDP) algorithm (17,38) in about 70 ms in the best case among100 trials, which is about 50 times shorter than that by the SA highlytuned in (17). [The SA in (17,19) is very fast by putting all the elementsof the coupling matrix Jon a cache of a single core. Thus, parallel com-puting with multiple cores cannot accelerate the SA because of commu-nication overheads.] In comparison with this, our single-FPGA SBmachine reaches the GW-SDP value in only 58 ms even in the worst caseamong 100 trials, as shown in Fig. 2A.Anothermainresultin(17) is that the CIM took only 5 ms to obtainas good solutions (large cut values) as the highly tuned SA obtained in50 ms, where the cut value of the MAX-CUT problem is given byEIsing214∑Ni¼1∑Nj¼1Ji;jwith Ising parameters (see the SupplementaryMaterials). Figure 2B shows that our SB machine takes only 0.5 ms to obtain better solutions on average than both the CIM in 5 ms and theSA in 50 ms.
]



> Komiwojadzera też mozęsz rozwiązać w czasie liniowym, tylko niedokładnie.
> pytanie czy P=NP dotyczy znajdowania ścisłego, optymalnego rozwiązania. 
> Ale dla wielu rzeczywistych przpadków takie przybliżone
> rozwiązanie jest wystarczająco dobre. 
> 
> I tu zaproponowali takie przylizone rozwiązanie*) dla jakeigoś
> problemu kombinarytorycznego, coś z modelem Isinga. 
> 
> https://www.researchgate.net/publication/332535366_Combinatorial_optimization_by_simulating_adiabatic_bifurcations_in_nonlinear_Hamiltonian_systems
> 
> Porównują się do symulowanego wyzarzania i jakeigoś algorytmu 
> zaprojektowanego pos isinga. 

Na to wygląda.


> *) kantowy w sumie daje to samo:)


Podali za dużo literatury pomocniczej jak na rozrywkę przy śniadaniu ;-)


Pozdrawiam