電力系統(tǒng)潮流計(jì)算中的稀疏技術(shù)研究

劉 濤

（太原供電分公司，山西 太原 030012）

1 引言

電力系統(tǒng)中潮流分布是指系統(tǒng)中電壓和功率的穩(wěn)態(tài)分布。根據(jù)電力系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)和功率、電壓等物理量量測(cè)等系統(tǒng)運(yùn)行狀況的邊界條件，來(lái)求解潮流分布的計(jì)算即潮流計(jì)算。潮流計(jì)算反映了電力系統(tǒng)的詳細(xì)運(yùn)行狀態(tài)，可以幫助運(yùn)行、規(guī)劃人員分析系統(tǒng)在給定條件下的穩(wěn)態(tài)運(yùn)行特點(diǎn)。潮流計(jì)算是電力系統(tǒng)中最基本、最重要的計(jì)算，是電力系統(tǒng)運(yùn)行、規(guī)劃以及安全性、可靠性分析和優(yōu)化的基礎(chǔ)，也是各種電磁暫態(tài)和機(jī)電暫態(tài)分析的基礎(chǔ)和出發(fā)點(diǎn)。

最優(yōu)潮流是數(shù)學(xué)最優(yōu)化理論在電力系統(tǒng)中的應(yīng)用，同時(shí)考慮了經(jīng)濟(jì)性和安全性，統(tǒng)籌兼顧、全面規(guī)劃，是電力系統(tǒng)中不可缺少的分析工具，在實(shí)際電力系統(tǒng)運(yùn)行中具有重要意義。

本文研究了潮流計(jì)算與最優(yōu)潮流的最新成果，并重點(diǎn)研究了運(yùn)用計(jì)算機(jī)在解決潮流計(jì)算問(wèn)題中的核心技術(shù)——稀疏技術(shù)，包括稀疏存儲(chǔ)和稀疏計(jì)算。

2 潮流計(jì)算與最優(yōu)潮流理論

2.1 潮流計(jì)算理論

潮流計(jì)算在數(shù)學(xué)上是求解一組由潮流方程描述的非線性方程組。20世紀(jì)50年代，隨著計(jì)算機(jī)的出現(xiàn)和計(jì)算機(jī)技術(shù)的發(fā)展，研究者開始使用計(jì)算機(jī)數(shù)學(xué)模擬方法進(jìn)行潮流計(jì)算。最初通過(guò)計(jì)算機(jī)實(shí)現(xiàn)的潮流計(jì)算方法是以導(dǎo)納矩陣為基礎(chǔ)的高斯迭代方法（Gauss方法），該方法內(nèi)存需要少，但是收斂性較差。而以阻抗矩陣為基礎(chǔ)的潮流算法，收斂性較好，但大大增加了內(nèi)存使用量，無(wú)法適用于大規(guī)模電力系統(tǒng)。牛頓-拉夫遜（Newton-Raphson，N-R）方法是求解非線性代數(shù)方程組的一種方法，在潮流計(jì)算中得到應(yīng)用。20世紀(jì)60年代之后，隨著Tinney等人提出稀疏矩陣技術(shù)和節(jié)點(diǎn)優(yōu)化編號(hào)方法，使得牛頓-拉夫遜方法的求解效率大大增加、求解規(guī)模大大增加。在20世紀(jì)90年代，潮流計(jì)算已經(jīng)被廣泛應(yīng)用于電力系統(tǒng)分析，各種算法都已經(jīng)實(shí)用化?，F(xiàn)階段關(guān)于潮流計(jì)算的研究，主要包含兩個(gè)方面：

（1）對(duì)于核心算法的研究。如對(duì)牛頓-拉夫遜方法或者快速分解發(fā)進(jìn)行改進(jìn)，以取得更好的計(jì)算速度等；或者將人工神經(jīng)網(wǎng)絡(luò)、粒子群、遺傳算法等新的數(shù)學(xué)方法引入潮流計(jì)算；或者對(duì)于新的數(shù)學(xué)模型，如電流注入模型的研究。

（2）對(duì)于提高潮流計(jì)算速度的研究。如對(duì)于稀疏技術(shù)或者節(jié)點(diǎn)優(yōu)化方法的進(jìn)一步研究；或者將并行計(jì)算技術(shù)應(yīng)用于潮流計(jì)算。

2.2 最優(yōu)潮流理論

潮流計(jì)算是最優(yōu)潮流的基礎(chǔ)，最優(yōu)潮流是潮流計(jì)算的一種擴(kuò)展。在潮流計(jì)算中，當(dāng)改變系統(tǒng)運(yùn)行的邊界情況時(shí)，系統(tǒng)的潮流分布也會(huì)隨之改變。電力系統(tǒng)中存在一些可調(diào)可控變量，如發(fā)電機(jī)的有功功率，調(diào)相機(jī)的控制電壓或者無(wú)功輸出功率，可投切的電容電抗器，有載調(diào)壓變壓器的變比等可以由運(yùn)行人員進(jìn)行控制，將這些可控變量記作μ。則控制變量μ值不同時(shí)，潮流分布不同。而潮流分布決定了系統(tǒng)的運(yùn)行效益，如系統(tǒng)網(wǎng)損、系統(tǒng)的總發(fā)電費(fèi)用等，故控制變量μ值會(huì)影響系統(tǒng)的運(yùn)行效益。最優(yōu)潮流就是在滿足系統(tǒng)負(fù)荷平衡和系統(tǒng)運(yùn)行的安全約束等條件下，尋找控制變量μ值，使得系統(tǒng)的運(yùn)行效益最高。最優(yōu)潮流在數(shù)學(xué)上是一個(gè)非線性規(guī)劃問(wèn)題，在網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)，系統(tǒng)的負(fù)荷給定等條件下，試確定系統(tǒng)的控制變量μ值，使得描述系統(tǒng)運(yùn)行的某一給定目標(biāo)函數(shù)取極小值。

最優(yōu)潮流方法眾多。如可以按照其處理約束條件的不同分為罰函數(shù)類、Kuhn-Tucker罰函數(shù)類和Kuhn-Tucker類?？梢园凑招拚淖兞靠臻g進(jìn)行分類，分為直接方法和簡(jiǎn)化方法，前者同時(shí)修正全空間變量μ和x，而后者只修正控制變量μ，狀態(tài)變量通過(guò)約束方程求解得到。也可以按照變量修正的方向進(jìn)行分類：第一類為梯度類算法，具有一階收斂性，如最速下降法；第二類為擬牛頓法，收斂性介于一階和二階之間，如各種變尺度方法；第三類為牛頓法，具有二階收斂性，例如Hessian矩陣法。

3 稀疏技術(shù)研究

稀疏技術(shù)的引入，是電力系統(tǒng)計(jì)算的一次革命。電力系統(tǒng)分析計(jì)算中廣泛涉及與矩陣、矢量相關(guān)的運(yùn)算。由于電力系統(tǒng)本身的結(jié)構(gòu)特點(diǎn)，如一條母線往往只跟周圍的幾條母線有直接的電氣聯(lián)系，使得反映網(wǎng)絡(luò)結(jié)構(gòu)的矩陣只有少量的非零元，是一個(gè)稀疏矩陣。稀疏技術(shù)可以分為稀疏矩陣技術(shù)和稀疏矢量技術(shù)。在涉及稀疏矩陣和稀疏矢量的運(yùn)算中，零元是沒(méi)有必要參與運(yùn)算的，也沒(méi)有必要對(duì)其進(jìn)行存儲(chǔ)。如果能夠做到“排零運(yùn)算”和“排零存儲(chǔ)”，能夠減少計(jì)算程序的內(nèi)存使用量、減少浮點(diǎn)運(yùn)算量，從而加快運(yùn)算速度。電力系統(tǒng)規(guī)模越大，稀疏技術(shù)帶來(lái)的效益越明顯。稀疏矩陣技術(shù)在各種電力系統(tǒng)分析計(jì)算中被廣泛采用。

3.1 排零存儲(chǔ)

電力系統(tǒng)分析中存在著大量的稀疏矩陣和稀疏矢量。為實(shí)現(xiàn)“排零存儲(chǔ)”，需要使用特定的格式，只存儲(chǔ)其中的非零元和其檢索信息。

稀疏矢量的存儲(chǔ)比較簡(jiǎn)單，只需要存儲(chǔ)非零元和非零元的下標(biāo)。稀疏矩陣的存儲(chǔ)格式眾多，實(shí)際程序設(shè)計(jì)中根據(jù)矩陣的稀疏結(jié)構(gòu)以及所采用的算法的特點(diǎn)，選擇合適的存儲(chǔ)方法。比較常見的稀疏矩陣的存儲(chǔ)格式有3種，即Coordinate、CSR和CSC。下面通過(guò)舉例說(shuō)明的形式介紹這3種常用的稀疏矩陣存儲(chǔ)格式。

3.1.1 Coordinate Format

Coordinate Format，又稱散居格式，是最簡(jiǎn)單稀疏存儲(chǔ)方式。本文大量使用的內(nèi)點(diǎn)算法數(shù)學(xué)包IPOPT就是使用的Coordinate格式對(duì)Jacobian、Hessian矩陣進(jìn)行存儲(chǔ)。Coordinate Format的優(yōu)點(diǎn)是非零元在values、rows和columns數(shù)組中的位置可以任意排列。缺點(diǎn)是因其存儲(chǔ)順序無(wú)規(guī)律，檢索難度大。

舉例說(shuō)明如下：

矩陣A的維數(shù)為n=5，A矩陣中非零元個(gè)數(shù)為nz=13。

Coordinate Format以one-based indexing的存儲(chǔ)方式如下：

values=1-1-3-2 5 4 6 4-4 2 7 8-5

rows=1 1 1 2 2 3 3 3 4 4 4 5 5

columns=1 2 3 1 2 3 4 5 1 3 4 2 5

其中values、rows、columns的長(zhǎng)度都為nz。三個(gè)數(shù)組依次記錄了C矩陣中非零元的數(shù)值，其所處的行位置，和其所處的列位置。

3.1.2 CSR Format

CSR（compressed sparse row），行壓縮格式。CSR被各種稀疏矩陣運(yùn)算數(shù)學(xué)軟件所支持，如IntelMKL和SuperLU。相比于Coordinate格式，CSR存儲(chǔ)格式檢索方便：可以方便檢索第i行的所有元素，從而可以方便檢索第i行的第j列的元素，即檢索元素B（i，j）。另外，CSR格式使用的存儲(chǔ)空間比Coordinate格式還要更少。

舉例說(shuō)明如下：

對(duì)于上述矩陣A，維數(shù)為n=5，非零元個(gè)數(shù)為nz=13。

CSR格式存儲(chǔ)結(jié)構(gòu)如下（one-based indexing）：

values=1-1-3-2 5 4 6 4-4 2 7 8-5

columns=1 2 4 1 2 3 4 5 1 3 4 2 5

row Index=1 4 6 9 12 14

rowIndex中依次記錄了上三角矩陣每一行中第一個(gè)非零元在columns和value數(shù)組中的位置。比如，row Index中的第二個(gè)元素為4，意味著columns和values數(shù)組中從第四個(gè)元素開始為原矩陣B中的上三角第二行的內(nèi)容。

3.1.3 CSC Format（Harwell-Boeing）

CSC（compressed sparse column），列壓縮格式。與行壓縮格式類似，只不過(guò)rowIndex變?yōu)閏olumnIndex。著名的稀疏矩陣算例集Harwell-Boeing Sparse Matrix Collection，就都是使用的CSC（也叫做Harwell-Boeing）格式。

舉例說(shuō)明如下：

對(duì)于上述矩陣A，維數(shù)為n=5，非零元個(gè)數(shù)為nz=13。

CSC Format下的存儲(chǔ)結(jié)構(gòu)如下（one-based indexing）：

values=1-1-3-2 5 4 6 4-4 2 7 8-5

columns=1 2 4 1 2 3 4 5 1 3 4 2 5

coIIndex=1 4 7 9 12 14

3.2 排零運(yùn)算

稀疏矩陣和稀疏矢量的運(yùn)算特點(diǎn)是“排零運(yùn)算”。因?yàn)榱悴挥绊懠訙p法，乘以任何數(shù)結(jié)果為零。即只要知道運(yùn)算中有一個(gè)操作數(shù)是零，計(jì)算機(jī)不必做浮點(diǎn)計(jì)算，就可以知道其結(jié)果。

舉例說(shuō)明如下：比如對(duì)n×n階矩陣進(jìn)行LU分解，將其分解成一個(gè)下三角矩陣L和一個(gè)單位上三角矩陣U的乘積。LU分解可以分為兩步：①按行規(guī)劃運(yùn)算；②消去運(yùn)算或者更新運(yùn)算。

具體計(jì)算時(shí)，排零運(yùn)算應(yīng)根據(jù)稀疏矩陣的存儲(chǔ)格式去設(shè)計(jì)相應(yīng)的計(jì)算方法，盡可能地去減少判斷運(yùn)算（判斷某個(gè)元素是不是零元）和浮點(diǎn)運(yùn)算。

實(shí)際實(shí)現(xiàn)時(shí)，為實(shí)現(xiàn)稀疏技術(shù)的排零運(yùn)算，可以采用各種第三方數(shù)學(xué)包。這些數(shù)學(xué)包往往支持各種稀疏矩陣的存儲(chǔ)結(jié)構(gòu)，并能夠快速求解各種稀疏矩陣、稀疏矢量的運(yùn)算。

比如NISTSparseBlas和SparseLib++（Netlib）都支持稀疏的BLAS運(yùn)算以及一些稀疏線性方程組的求解。前者是由美國(guó)國(guó)家標(biāo)準(zhǔn)局（NIST，National Institute of Standards and Technology）根據(jù)BLAST規(guī)范實(shí)現(xiàn)的稀疏BLAS計(jì)算包，由C++語(yǔ)言編寫，僅包含3個(gè)頭文件和1個(gè)源文件，使用簡(jiǎn)單；后者功能強(qiáng)大，支持矩陣的文本輸入輸出，支持LU分解和Cholesky分解等。一些主流的商業(yè)計(jì)算軟件如IntelMKL和NAG等也都支持各種稀疏矩陣格式及各種稀疏矩陣運(yùn)算。

4 結(jié)論

潮流計(jì)算是電力系統(tǒng)中最基本、最重要的計(jì)算，是電力系統(tǒng)運(yùn)行、規(guī)劃以及安全性、可靠性分析和優(yōu)化的基礎(chǔ)，也是各種電磁暫態(tài)和機(jī)電暫態(tài)分析的基礎(chǔ)和出發(fā)點(diǎn)。通過(guò)研究發(fā)現(xiàn)，隨著計(jì)算機(jī)性能和潮流計(jì)算算法的改進(jìn)，潮流計(jì)算的計(jì)算規(guī)模和計(jì)算速度都得到了顯著的提高。在這些算法當(dāng)中，稀疏技術(shù)的應(yīng)用和完善具有重要意義。通過(guò)使用第三方公司開發(fā)的數(shù)學(xué)包，可以大幅提高運(yùn)用計(jì)算機(jī)實(shí)現(xiàn)稀疏技術(shù)的開發(fā)效率，這是具有實(shí)際意義的。

[1] 姚玉斌，魯寶春，陳學(xué)允.1999：《小阻抗支路對(duì)牛頓法潮流的影響及其處理方法》，電網(wǎng)技術(shù)，23（9）：27～31.

[2] 朱凌志，安寧.2005：《基于二維鏈表的稀疏矩陣在潮流計(jì)算中的應(yīng)用》，電網(wǎng)技術(shù)，29（8）：16～19.

[3] 王守相，王成山.2003：《配電系統(tǒng)節(jié)點(diǎn)優(yōu)化編號(hào)方案比較》電力系統(tǒng)自動(dòng)化，27（8）：54～58.