計算機代數

數學計算機科學中,[1]計算機代數符號計算代數計算,是研究、開發用於操作表達式數學物件算法軟件的科學領域。這通常被視為是運算科學的一個子領域,但運算科學一般基於近似浮點數數值計算,而符號計算則使用含變量的表達式進行精確計算,其中變量沒有賦值。 執行符號計算的軟件系統稱為計算機代數系統,「系統」暗示了軟件的複雜性,其中至少包括一種在計算機中表示數學數據的方法、一種程式語言(通常異於用於實現的語言)、一種專門的內存管理器、一套供輸入輸出表達式的用戶界面、一大套用於通常運算的子程序,如表達式簡化、能實現連鎖律多項式因式分解不定積分等等的求導算法。

用計算機代數系統公理代數函數進行符號積分

計算機代數被廣泛用於數學實驗、設計數值程序所用的公式。純數值方法失效時,計算機代數也可用於完整的科學計算,這見於公開密鑰加密和一些非線性問題。

術語

有些學者區分「計算機代數」(computer algebra)與「符號計算」(symbolic computation),後者指數學公式計算之外的符號計算。有人則用「符號計算」表示計算機科學方面的內容,而用「計算機代數」表示數學方面的內容。[2]

科學界

目前還沒有計算機代數領域的專門學會,這一職能由計算機協會的特別興趣小組(special interest group)SIGSAM承擔。[3]

計算機代數領域有多個年會,最重要的是由SIGSAM定期主辦的ISSAC(符號與代數計算國際研討會)。[4]

有幾種專門研究計算機代數的期刊,其中最重要的一種是由Bruno Buchberger於1985年創辦的《符號計算》(Journal of Symbolic Computation)。[5]其他一些期刊也定期發表計算機代數方面的文章。[6]

計算機科學

數據表示

由於數值軟件在進行數值計算時的效率很高,因此在計算機代數中,通常用精確數據進行精確計算。這意味着即使輸出規模很小,計算過程的中間數據也可能不可預測地增長,這種行為稱為表達式膨脹(expression swell)。為解決這問題,數據表示和處理算法中有各種各樣的方法。

數字

數值計算最常用的數字系統是浮點數和大小固定的整數。由於表達式膨脹,這些系統都不便於計算機代數。[7]

因此,計算機代數使用的基數是數學整數,通常用某個底數(一般是機器允許的最大底數)的無界有符序列表示。從整數可以定義有理數

為高效算術運算編程是一項艱巨的任務,因此大多數免費的計算機代數系統和商業系統,如MathematicaMaple都使用GMP庫,它也因此成為事實上的標準。

表達式

 
表達式(8 − 6) × (3 + 1)LISP樹形式,來自1985年的一篇碩士論文。[8]

數字變量外,每個表達式都可看做是跟着操作數序列的算符。在計算機代數軟件中,表達式通常都這樣表示,許多看似不是表達式的東西都可以這樣表示和操作,非常靈活。例如,方程是以「=」為算符的表達式,矩陣可表為以「矩陣」為算符、行為操作數的表達式。

連程序也可以看做是以「過程」為算符、含至少兩個操作數(參數列表與內容)的表達式,內容也是以「正文」為算符、以指令為操作數的表達式。反過來,表達式也可以看成程序:a + b可看做加法運算程序,參數是ab。執行這個程序即對給定值的ab表達式求值;若無給定值,則求值結果就是輸入。

這種「延遲求值」在計算機代數中是最基本的。例如,等式中的「=」也是等式檢驗程序的名稱:通常,等式求值結果仍是等式,但進行檢驗時,無論是用戶通過「求布林值」命令提出明確要求,還是系統在程序內部啟動的自動檢驗,都會執行求值為布林值的結果。

由於表達式操作數的規模無法預測,而且在過程中可能變化,因此操作數序列通常用指針序列(如Macsyma)或哈希表元素序列(如Maple)。

簡化

在表達式 上直接應用關於x求導基本規則,可得

 

一般來說,我們需要比這更簡單的表達式,需要簡化。

這一般通過重寫邏輯完成。[9]有幾類重寫邏輯值得考慮,最簡單的是總要縮減表達式,例如EE → 0sin(0) → 0。它們被系統地用於計算機代數系統。

加法、乘法這種有結合律的運算的混合會帶來困難。處理結合運算的標準方法是,考慮其操作數是任意的,即將a + b + c表示為"+"(a, b, c)。因此a + (b + c)(a + b) + c 都能簡化為"+"(a, b, c),展示為a + b + c。對於ab + c這樣的表達式,最簡單的辦法是系統地將EEFE/F分別改寫為(−1)⋅EE + (−1)⋅FEF−1。換句話說,表達式的內部表示中,數字的表示沒有減法、除法或一元負號。

加法和乘法的交換律也是一個難點。問題在於如何快速識別同類項。對很長的和或積來說,測試每對項的成本都很高。Macsyma排序了和與積的操作數,將同類項放在連續位置上,這樣就可以輕鬆檢測出來。Maple則使用了散列函數,輸入同類項時會產生碰撞,由此可以立即合併。這樣,計算中多次出現的子式就能被立即識別,並只儲存一次,這樣就避免了重複操作,從而節省內存並加快計算速度。

部分重寫規則有時會增加表達式的大小,有些會減小,例如分配律三角恆等式。具體來說,分配律允許  。這類重寫規則沒有很好的決策方式,一般交給用戶決定。實現分配的計算機函數通常叫做「展開」,反向則是「因式分解」,需要一種非平凡算法,因此是計算機代數系統的一個關鍵功能。

數學

在計算機中處理表達式時會出現一些基本數學問題。我們主要考慮多元有理函數,這不是嚴格的限制,因為表達式中出現的無理函數一旦被簡化,通常都會被視為新的不定項,例如

 

視為  組成的多項式。

等式

表達式而言,有兩種等價關係。語法相等指在計算機中的表示相等,這在程序中很容易測試;語義相等指兩個表達式表示相同的數學物件,如

 

理查森定理可知,若表達式中允許指數或對數,便可能不存在算法可判斷代表數字的的兩式是否語義相等。因此,只能對多項式有理函數等部分表達式進行(語義)等價測試。

要測試兩式是否登記愛,通常都不用特別設計算法,而是將表達式置於某個規範形中,或將差置於標準形中,再測試結果的語義等價。

在計算機代數中,「規範形」與「標準形」不是同義詞。[10]「規範形」(canonical form)是指只有語法相等時才語義相等;「標準形」(normal form)是指只有語法上為0時,才在語義上為0.換句話說,0在標準形表達式中有唯一形式。

標準形是計算機代數的首選,有以下幾個原因。首先,規範形的計算成本可能更高。例如,求多項式規範形必須要展開每個積,而標準形不需要(下詳)。其次,與含根式的表達式類似,規範形(如果存在)取決於一些任意的選擇,對於獨立計算的兩式可能是不同的。這就使得規範形的使用變得不切實際。

歷史

計算機代數起源於約1970年,當人們首次將聞名已久的算法應用於計算機時發現其效率非常低。[11]因此,研究者的主要工作是重新應用經典代數,以使其生效,並構造實現它們的高效算法。一個典型例子是計算多項式最大公因數,是簡化分式必須的。令人驚訝的是,經典的輾轉相除法對無窮域上的多項式效率很低,因此需要開發新的算法。線性代數的經典算法也如此。

另見

參考文獻

  1. ^ ACM Association in computer algebra. [2023-09-16]. (原始內容存檔於2023-07-30). 
  2. ^ Watt, Stephen M. Making Computer Algebra More Symbolic (Invited) (PDF). Transgressive Computing 2006: A conference in honor of Jean Della Dora, (TC 2006): 43–49. 2006 [2023-09-16]. ISBN 9788468983813. OCLC 496720771. (原始內容存檔 (PDF)於2022-05-26). 
  3. ^ SIGSAM official site. [2023-09-16]. (原始內容存檔於2023-08-16). 
  4. ^ SIGSAM list of conferences. [2012-11-15]. (原始內容存檔於2013-08-08). 
  5. ^ Cohen, Joel S. Computer Algebra and Symbolic Computation: Mathematical Methods . AK Peters. 2003: 14. ISBN 978-1-56881-159-8. 
  6. ^ SIGSAM list of journals. [2023-09-16]. (原始內容存檔於2013-09-28). 
  7. ^ Richard Liska Expression swell頁面存檔備份,存於互聯網檔案館), from "Peculiarities of programming in computer algebra systems"
  8. ^ Cassidy, Kevin G. The Feasibility of Automatic Storage Reclamation with Concurrent Program Execution in a LISP Environment (PDF) (學位論文). Naval Postgraduate School, Monterey/CA: 15. Dec 1985. ADA165184. 
  9. ^ Buchberger, Bruno; Loos, Rüdiger. Algebraic simplification (PDF). Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf (編). Computer Algebra: Symbolic and Algebraic Computation. Computing Supplementa 4. 1983: 11–43 [2023-09-16]. ISBN 978-3-211-81776-6. doi:10.1007/978-3-7091-7551-4_2. (原始內容存檔 (PDF)於2022-01-20). 
  10. ^ Davenport, J. H.; Siret, Y.; Tournier, É. Computer Algebra: Systems and Algorithms for Algebraic Computation. Academic. 1988. ISBN 0-12-204230-1. OCLC 802584470. 
  11. ^ Kaltofen, Erich. Factorization of polynomials. Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf (編). Computer Algebra: Symbolic and Algebraic Computation. Computing Supplementa 4. 1983: 95–113. ISBN 978-3-211-81776-6. S2CID 18352153. doi:10.1007/978-3-7091-7551-4_8. 

閱讀更多

For a detailed definition of the subject:

For textbooks devoted to the subject: