電腦代數與符號計算

表達式膨脹(expression swell)

你給電腦代數系統一個答案乾淨的乾淨問題,過程中某處機器卻磨到停擺、或耗盡記憶體——儘管輸入與最終結果都很小。元兇就是表達式膨脹:精確的中間結果即使起點與終點都不大,也會在大小上爆炸性成長的傾向。它是符號計算最重要的單一實務限制。

為什麼保持精確的代價這麼大?因為精確性禁止了原本會讓數保持小的捨入。在精確有理數算術裡,反覆運算會堆出龐大的分子與分母,直到最後一次最大公因數約分把它們縮回。在天真的有理數多項式最大公因式裡,即使答案微小,中間係數也劇烈膨脹。透過葛羅布納基底解多項式系統,可能產生雙重指數大小的中間多項式。此模式是普遍的:數值方法每步都捨入而維持同樣大小,但符號方法必須把每個精確的位數與符號往前帶,而那些會累積。經典的畫面是無分數版的高斯消去,其元素隨每個樞紐幾何成長。

表達式膨脹正是為什麼「就精確地做嘛」很少是數值方法的免費升級,也是為什麼電腦代數系統在小實例上出色、放大一號卻無能為力的原因。解法正是電腦代數的聰明所在:把分數保持約分;用子結式方法限制最大公因式的係數成長;而最重要的是使用模運算與 p 進技術——在數個質數模下算出答案(那裡數保持又小又有界),再用中國剩餘定理或亨澤爾提升重建精確結果,完全繞開膨脹的中間量。機率性與混合符號-數值方法也追求同一目標。認出並化解表達式膨脹,是實務符號計算技藝的大半。

對一個 10 乘 10、由小整數組成的矩陣跑天真的(帶分數的)高斯消去,全程保持精確。樞紐產生的分數,其分子分母幾乎每步都成長,於是中間矩陣可能容納數千位長的數——儘管最終的精確解元素都很小。無分數版消去或模運算方法能讓那些巨怪根本不出現。

輸入與輸出微小、中間卻巨怪——表達式膨脹的標誌。

表達式膨脹不是可以打補丁修掉的臭蟲——它是「要求精確」的內在屬性。你管理它(約分分數、子結式、模運算/p 進重建),而非消除它。當膨脹使符號計算變得不可行,改用數值或混合方法往往是唯一現實的選擇。

又称
intermediate expression swellcoefficient growth中間表達式膨脹係數膨脹