Representasi formal cincin dalam perhitungan

17

Saat membaca makalah tentang menggunakan metode aljabar untuk mendeteksi beberapa subgraf yang diinduksi, tampak bahwa edge ideal adalah alat penting yang menghubungkan teori aljabar dan grafik komutatif. Karena saya tidak terbiasa dengan perhitungan objek aljabar, apakah ada referensi atau buku yang bagus tentang topik ini? Keistimewaan dalam merepresentasikan cincin R pada mesin Turing, dan kompleksitas menentukan sifat-sifat dasar pada R (katakanlah, ketinggian ideal utama dalam R.)

Hsien-Chih Chang 張顯 之
sumber
Maaf jika pertanyaannya terlalu mendasar atau luas ...
Hsien-Chih Chang 張顯 之
itu pertanyaan yang bagus.
Suresh Venkat
4
Meskipun saya sendiri tidak tahu banyak tentang topik tersebut, saya akan merekomendasikan untuk memeriksa On the Ring Isomorphism dan Automorphism Problems oleh Kayal dan Saxena. Ini adalah makalah teori yang sangat rumit, jadi itu akan membantu. Saya percaya mereka mewakili cincin hingga dengan terlebih dahulu menentukan kelompok aditif (oleh generatornya) dan kemudian memberikan daftar produk berpasangan dari semua generator ini.
Robin Kothari

Jawaban:

14

Pertanyaan Anda terkait dengan bidang (tidak ada kata pun yang dimaksudkan) yang disebut "Aljabar Komputer". Saya sendiri sedang mencari survei komprehensif ketika saya sedang mengerjakan metode aljabar untuk menghitung berbagai metrik sentralitas grafik. Saya tidak dapat menemukan survei yang bagus, tetapi sebagian buku ini bermanfaat. Makalah penelitian tentang "topik" ini tersebar di seluruh dan sering tidak secara eksplisit dikategorikan sebagai "aljabar komputer". Membaca makalah algoritmik tentang isomorfisme, anjak piutang (bilangan bulat / polinomial) dan algoritma grafik berdasarkan perkalian matriks mungkin memberi Anda lebih banyak wawasan.

Siwa Kintali
sumber
"Bidang" yang disebut Komputer "Aljabar" ... Hmm ... Pokoknya, terima kasih atas buku dan kata kuncinya sekarang saya dapat melakukan beberapa pencarian lebih lanjut !!
Hsien-Chih Chang 張顯 之
14

Setahu saya:

  1. Jika Anda membaca tentang batas bawah dalam beberapa model komputasi aljabar, maka asumsi umum adalah bahwa operasi cincin atau lapangan adalah biaya konstan , yaitu mereka diberikan sebagai primitif. Ini adalah asumsi yang dibuat dalam salah satu sumber utama pada topik: Burgisser, Clausen, Shokrollahi- Aljabar teori kompleksitas (Springer, 1997). (Dan inilah yang dimodelkan oleh sirkuit aljabar, misalnya.)

  2. Ketika seseorang berbicara tentang batas atas , untuk pertanyaan standar dalam kompleksitas aljabar, seperti ketika mempelajari prosedur pengujian identitas polinomial, maka asumsi standar adalah bahwa operasi cincin atau lapangan dapat dihitung dalam polytime. Ini berarti bahwa seseorang bekerja di atas bilangan bulat, atau lebih dari angka-angka rasional, dan mudah untuk menemukan skema pengkodean yang memungkinkan perhitungan operasi dasar yang efisien.

  3. Untuk tujuan lain yang saya ketahui, mengenai model aljabar, cara untuk mewakili cincin atau bidang adalah pertanyaan nyata dan kadang-kadang tidak ada cara yang efisien untuk melakukannya, dan bahkan mungkin ada pertanyaan tentang ketidakpastian. Referensi yang saya tahu yang mencakup pertanyaan-pertanyaan semacam ini adalah buku yang diberikan Siwa Kintali, dan juga: Aljabar Algoritma , Bhubaneswar Mishra, Springer 1993: Bab 3 membahas cara-cara untuk mewakili cincin tertentu.

Buku-buku lain yang menarik mungkin: Zur Gathen dan Jurgen Gerhard, Modern Computer Algebra , Cambridge, 1999. Dan mungkin Victor Shoup, Pengantar Komputasi untuk Teori Angka dan Aljabar , (Tersedia online).

Iddo Tzameret
sumber
Buku online sangat membantu !!
Hsien-Chih Chang 張顯 之
8

Anda juga mungkin beruntung dengan kata kunci 'aljabar komutatif komputasi' dan 'geometri aljabar komputasi.' Coba CLO sebagai titik awal, dan lihat J. Symbolic Computation, dan sistem seperti Macaulay2 dan Singular dan makalah yang mereferensikannya. Palu besar adalah pangkalan obner Gr, yang perhitungannya akan memecahkan banyak masalah aljabar, tetapi merupakan kasus terburuk yang eksponensial ganda secara umum.

Jason Morton
sumber