สมมติว่าฉันมีพื้นฐาน $B$ ของ $n$- ตาข่ายมิติ $L\subseteq\mathbb{Z}^n$ และ $B$ มี $n$ เวกเตอร์ ตอนนี้ฉันเอาอีก $v\in \mathbb{Z}^n\setลบ L$ และฉันกำหนดตารางใหม่ $L'=L+\mathbb{Z}v$. เซตของเวกเตอร์ $B':=B\cup\{v\}$ สร้าง $L'$, แต่ตั้งแต่ $L'$ เป็น $n$-มิติ มันแรงค์มากสุด $n$, ดังนั้น $B'$ ใหญ่เกินไป ดังนั้นจึงต้องมีพื้นฐานอื่นที่ทำให้เกิด $L'$. เราจะผลิตสิ่งนั้นได้อย่างไร $B'$?
ฉันจำการอ่านได้อย่างคลุมเครือว่า LLL สามารถทำได้ แต่ฉันไม่รู้ว่าจะทำอย่างไร ใครสามารถชี้อ้างอิงหรือให้ข้อโต้แย้ง / พิสูจน์ได้อย่างรวดเร็ว?
การเขียนคำตอบเพื่อไม่ให้ไม่มีคำตอบ แม้ว่าจะมีการกล่าวถึง HNF ในความคิดเห็นก็ตาม
Hermite Normal Form เป็นวิธีมาตรฐานในการลดชุดการสร้างให้เป็นพื้นฐาน ซึ่งหมายความว่าเป็นวิธีมาตรฐานในการคำนวณการดำเนินการหลายอย่างบนแลตทิซ (ซึ่งแสดงได้ง่ายในรูปของเวกเตอร์พื้นฐาน) ตัวอย่างเช่น
$L+L'$ (ซึ่งตัวอย่างของคุณเป็นกรณีพิเศษ) หรือ
$L\cap L'$ (สิ่งนี้ไม่ชัดเจนและต้องใช้ความเป็นคู่)
ดูปัญหาขัดแตะอย่างง่ายของ บันทึกเหล่านี้.
คุณแสดงความคิดเห็น
ดูเหมือนว่าการคำนวณ Hermite ในรูปแบบปกติอย่างมีประสิทธิภาพนั้นไม่ใช่เรื่องเล็กน้อย...
นี่เป็นเรื่องจริง แต่เรื่องไร้สาระนั้นยังห่างไกลจากคำว่า "ยาก" ฉันอ้างจากบันทึก
ไม่ยากที่จะคิดอัลกอริทึมที่คำนวณ HNF ของเมทริกซ์ที่มีการดำเนินการเป็นจำนวนพหุนามเท่านั้น อย่างไรก็ตาม วิธีแก้ปัญหาที่ไร้เดียงสาสำหรับปัญหานี้อาจส่งผลให้เกิดเวลาทำงานแบบซูเปอร์โพลิโนเมียล เนื่องจากตัวเลขในการคำนวณระดับกลางสามารถมีจำนวนมากได้อย่างง่ายดาย
บันทึกย่อที่เชื่อมโยงรวมถึงรหัสเทียมสำหรับการปรับใช้ HNF ที่เวลาทำงานพหุนาม (โดยการทำให้ค่ากลางอยู่ในขอบเขต) มันอาจจะซับซ้อนกว่า LLL เล็กน้อย แต่จริงๆแล้วไม่มากนัก --- ทั้งคู่เป็นอัลกอริทึมที่ฉันคาดหวังว่านักศึกษาระดับปริญญาตรี / รุ่นพี่จะสามารถนำไปใช้ได้โดยไม่ต้องใช้ความพยายามมากเกินไป
แน่นอน คุณสามารถใช้ความพยายามมากขึ้นเพื่อให้ได้สิ่งที่มีประสิทธิภาพมากขึ้น ดูบทความนี้ของ เพอร์เน็ตและสไตน์. เนื่องจาก Stein เป็นผู้ก่อตั้ง Sage CAS ฉันจึงคิดว่าสิ่งนี้ค่อนข้างใกล้เคียงกับที่ Sage นำมาใช้ อย่างน้อยก็ประมาณปี 2011 อัลกอริทึมนี้อาจเป็นอัลกอริทึมที่ "ไม่สำคัญ" ที่คุณคิดไว้ แต่ในทางกลับกัน การนำ LLL ไปใช้อย่างมีประสิทธิภาพก็ไม่ใช่เรื่องเล็กน้อยเช่นกัน (ฉันเคยได้ยินเมื่อไม่กี่ปีที่ผ่านมาว่า LLL เป็นเวลาพหุนามพร้อมกัน และอาจเป็นเรื่องยากที่จะรันบนแลตทิซขนาดใหญ่ พูดถึงมิติ 1k+)
เป็นมูลค่าการกล่าวขวัญว่าดูเหมือนจะมีงานบางอย่างที่คำนวณ HNF โดยใช้ LLL เป็นรูทีนย่อย ดูตัวอย่าง นี้.
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
