Upaya Komputasi dari Algoritma

9

Pertimbangkan masalah optimisasi cembung yang tidak dibatasi ketatBiarkan x_ \ text {opt} menunjukkan minima uniknya dan x_0 menjadi perkiraan awal yang diberikan kepada x_ \ text {opt}. Kami akan memanggil vektor x solusi \ epsilon- close dari \ mathcal {O} jika \ begin {persamaan} \ frac {|| x - x _ {\ text {opt}} || _2} {|| x_0 - x_ \ text {opt} || _2} \ leq \ epsilon. \ end {persamaan}x opt x 0 x opt . x ϵ -O:=minxRnf(x).xoptx0xopt.xϵO

||xxopt||2||x0xopt||2ϵ.

Misalkan terdapat dua algoritma iteratif A1 dan A2 untuk menemukan solusi ϵ close dari O dengan properti berikut:

  1. Untuk setiap ϵ>0, upaya komputasi total, yaitu upaya yang diperlukan per iterasi × jumlah total iterasi, untuk menemukan solusi ϵ close sama untuk kedua algoritma.
  2. Upaya per iteration untuk A1 adalah O(n), katakanlah, sementara itu dari A2 adalah O(n2).

Apakah ada situasi, di mana satu lebih suka satu algoritma daripada yang lain? Mengapa?

Suresh
sumber

Jawaban:

14

Biasanya sangat sulit jika bukan tidak mungkin untuk mengimplementasikan versi paralel dari algoritma iteratif yang melumpuhkan antar iterasi. Penyelesaian satu iterasi adalah titik urutan alami. Jika satu algoritma membutuhkan lebih sedikit iterasi tetapi lebih banyak kerja per iterasi, maka kemungkinan besar algoritma ini dapat secara efektif diimplementasikan secara paralel.

Contohnya adalah pemrograman linier, di mana metode penghalang primal-dual (titik interior) biasanya menggunakan hanya beberapa lusin iterasi bahkan untuk masalah yang sangat besar, tetapi pekerjaan per iterasi cukup luas. Sebagai perbandingan, berbagai versi metode simpleks biasanya membutuhkan iterasi yang jauh lebih banyak, tetapi kerja per iterasi lebih sedikit. Dalam prakteknya, implementasi paralel dari metode titik interior telah menunjukkan efisiensi paralel yang jauh lebih baik daripada implementasi paralel dari metode simpleks.

Brian Borchers
sumber
7

Saya dapat memikirkan beberapa kemungkinan:

Jika kedua algoritma secara monoton mengurangi kesalahan dengan setiap iterasi, maka mungkin lebih disukai beberapa untuk memiliki lebih banyak, iterasi lebih murah karena memberikan Anda lebih banyak pilihan tentang kapan harus berhenti iterasi.

Jika adalah bekerja dan waktu tetapi memori , Anda mungkin lebih suka jika besar. bahkan mungkin cukup besar untuk membuat Anda memilih karena penggunaan memori lebih cenderung menghambat Anda di sini. O(n)O( n k ) A 2 kk=2 A 2A1O(n)O(nk)A2kk=2A2

Ini mungkin berlaku apakah kita berbicara tentang optimasi atau masalah iteratif lainnya.

Bill Barth
sumber
Saya setuju dengan Anda sehubungan dengan kendala ruang. Saya bertanya-tanya apakah seseorang dapat membuat kasus hanya berdasarkan kompleksitas waktu.
Suresh