Operaciones de matriz dispersa

Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Eficiencia de las operaciones

Complejidad computacional
Detalles algorítmicos

Complejidad computacional

La complejidad computacional de las operaciones dispersas es proporcional al número de elementos distintos de cero en la matriz.nnz La complejidad computacional también depende linealmente del tamaño de la fila y del tamaño de la columna de la matriz, pero es independiente del producto, el número total de cero y los elementos distintos de cero.mnm*n

La complejidad de las operaciones bastante complicadas, como la solución de ecuaciones lineales dispersas, involucra factores como ordenar y rellenar, que se discuten en la sección anterior. En general, sin embargo, el tiempo de equipo necesario para una operación de matriz dispersa es proporcional al número de operaciones aritméticas en cantidades distintos de cero.

Detalles algorítmicos

Las matrices dispersas se propagan a través de cálculos según estas reglas:

Las funciones que aceptan una matriz y devuelven un vector escalar o de tamaño constante siempre producen la salida en formato de almacenamiento completo. Por ejemplo, la función siempre devuelve un vector completo, si su entrada es completa o dispersa.size
Las funciones que aceptan escalares o vectores y devuelven matrices, como,, y, siempre devuelven resultados completos.zerosonesrandeye Esto es necesario para evitar la introducción de la dispersión inesperadamente. El análogo disperso de es simplemente.zeros(m,n)sparse(m,n) Los análogos dispersos de y son y, respectivamente.randeyesprandspeye No hay ningún análogo disperso para la función.ones
Las funciones unarias que aceptan una matriz y devuelven una matriz o un vector conservan la clase de almacenamiento del operando. Si es una matriz dispersa, entonces es también una matriz dispersa, y es un vector disperso.Schol(S)diag(S) Funciones columnwise como y también devuelven vectores dispersos, aunque estos vectores pueden ser completamente distintos de cero.maxsum Las excepciones importantes a esta regla son las y funciones.sparsefull
Los operadores binarios producen resultados dispersos si ambos operandos son escasos y los resultados completos si ambos están llenos. Para los operandos mixtos, el resultado es completo a menos que la operación conserve la dispersión. Si es escaso y está lleno, entonces, y está lleno, mientras que y es escaso.SFS+FS*FF\SS.*FS&F En algunos casos, el resultado puede ser escaso aunque la matriz tenga pocos elementos cero.
La concatenación de matrices mediante la función o los corchetes produce resultados dispersos para operandos mixtos.cat

Una permutación de las filas y columnas de una matriz dispersa se puede representar de dos maneras:S

Una matriz de permutación actúa en las filas de as o en las columnas como.PSP*SS*P'
Un vector de permutación, que es un vector completo que contiene una permutación de, actúa sobre las filas de as, o en las columnas como.p1:nSS(p,:)S(:,p)

Por ejemplo:

p = [1 3 4 2 5] I = eye(5,5); P = I(p,:) e = ones(4,1); S = diag(11:11:55) + diag(e,1) + diag(e,-1)

p =       1     3     4     2     5   P =       1     0     0     0     0      0     0     1     0     0      0     0     0     1     0      0     1     0     0     0      0     0     0     0     1   S =      11     1     0     0     0      1    22     1     0     0      0     1    33     1     0      0     0     1    44     1      0     0     0     1    55

Ahora puede probar algunas permutaciones utilizando el vector de permutación y la matriz de permutación.pP Por ejemplo, las instrucciones y devuelven la misma matriz.S(p,:)P*S

S(p,:)

ans =      11     1     0     0     0      0     1    33     1     0      0     0     1    44     1      1    22     1     0     0      0     0     0     1    55

P*S

ans =      11     1     0     0     0      0     1    33     1     0      0     0     1    44     1      1    22     1     0     0      0     0     0     1    55

Del mismo modo, y ambos producenS(:,p)S*P'

S*P'

ans =      11     0     0     1     0      1     1     0    22     0      0    33     1     1     0      0     1    44     0     1      0     0     1     0    55

Si es una matriz dispersa, ambas representaciones usan el almacenamiento proporcional a y se puede aplicar a tiempo proporcional a.PnSnnz(S) La representación vectorial es un poco más compacta y eficiente, por lo que las diversas rutinas de permutación de matriz dispersa todos devuelven vectores de fila completa con la excepción de la permutación pivotante en la factorización LU (triangular), que devuelve una matriz compatible con la factorización completa de LU.

Para convertir entre las dos representaciones de permutación:

n = 5; I = speye(n); Pr = I(p,:); Pc = I(:,p); pc = (1:n)*Pc

pc =       1     3     4     2     5

pr = (Pr*(1:n)')'

pr =       1     3     4     2     5

El inverso de es simplemente.PR = P' Puede calcular el inverso de with.pr(p) = 1:n

r(p) = 1:5

r =       1     4     2     3     5

Reordenamiento para la Sparsity

Reordenar las columnas de una matriz a menudo puede hacer que su LU o los factores QR sparser. Reordenando las filas y columnas a menudo puede hacer que su Cholesky factores sparser. La más simple reordenación es ordenar las columnas por número distinto de cero. Esto es a veces un buen reordenamiento para matrices con estructuras muy irregulares, especialmente si hay una gran variación en los recuentos de filas o columnas distintos de cero.

Calcula una permutación que ordena las columnas de una matriz por el número de nonceros en cada columna de menor a mayor.colperm

Reordenar para reducir el ancho de banda

La orden inversa Cuthill-McKee está destinada a reducir el perfil o el ancho de banda de la matriz. No se garantiza que encuentre el ancho de banda más pequeño posible, pero normalmente lo hace. La función funciona realmente en la estructura distinta de cero de la matriz simétrica, pero el resultado también es útil para matrices no simétricas.symrcmA + A' Este orden es útil para matrices que provienen de problemas unidimensionales o problemas que son en cierto sentido.long and thin

Grado mínimo aproximado de ordenación

El grado de un nodo en un gráfico es el número de conexiones a ese nodo. Esto es lo mismo que el número de elementos fuera de la diagonal distinto de cero en la fila correspondiente de la matriz de adyacencia. El algoritmo de grado mínimo aproximado genera un orden basado en cómo estos grados se alteran durante la eliminación Gaussiana o factorización Cholesky. Es un algoritmo complicado y potente que generalmente conduce a factores de más disperso que la mayoría de las otras órdenes, incluyendo el conteo de columnas y reverso Cuthill-McKee. Debido a que mantener un registro del grado de cada nodo consume mucho tiempo, el algoritmo de grado mínimo aproximado utiliza una aproximación al grado, en lugar del grado exacto.

Estas funciones implementan el algoritmo de grado mínimo aproximado:MATLAB^®

— Se utiliza con matrices simétricas.symamd
: Se utiliza con matrices no simétricas y matrices simétricas del formulario o.colamdA*A'A'*A

Vea un ejemplo usando.Reordenación y factorizaciónsymamd

Puede cambiar varios parámetros asociados con los detalles de los algoritmos utilizando la función.spparms

Para obtener más información sobre los algoritmos utilizados por y, vea.colamdsymamd[5] El grado aproximado de uso de los algoritmos se basa en.[1]

Ordenación de disección anidada

Al igual que el orden de grado mínimo aproximado, el algoritmo de ordenación de disección anidada implementado por la función reordena las filas y columnas de la matriz al considerar que la matriz es la matriz de adyacencia de un gráfico.dissect El algoritmo reduce el problema a una escala mucho menor al contraer pares de vértices en el gráfico. Después de reordenar el pequeño gráfico, el algoritmo aplica los pasos de proyección y refinamiento para expandir el gráfico de nuevo al tamaño original.

El algoritmo de disección anidada produce reordenamientos de alta calidad y funciona particularmente bien con matrices de elementos finitos en comparación con otras técnicas de reordenación. Para obtener más información sobre el algoritmo de ordenación de disección anidada, consulte.[7]

Factorizar matrices dispersas

LU Factorization
Factorización Cholesky
La factorización de QR
Factorizaciones incompletas

LU Factorization

Si es una matriz dispersa, el siguiente comando devuelve tres matrices dispersas, y tal que.SLUPP*S = L*U

[L,U,P] = lu(S);

Obtiene los factores por eliminación Gaussiana con pivotantes parciales.lu La matriz de permutación solo tiene elementos distintos de cero.Pn Al igual que con las matrices densas, la declaración devuelve una matriz triangular inferior de la unidad permutada y una matriz triangular superior cuyo producto es.[L,U] = lu(S)S Por sí mismo, devuelve y en una sola matriz sin la información de pivote.lu(S)LU

La sintaxis de tres salidas se selecciona a través de pivotantes parciales numéricos, pero no pivotar para mejorar la dispersión en los factores.[L,U,P] = lu(S)PLU Por otro lado, la sintaxis de cuatro resultados se selecciona a través de la pivotante parcial de umbral, y selecciona y para mejorar la dispersión en los factores.[L,U,P,Q] = lu(S)PPQLU

Puede controlar la pivotante en matrices dispersas utilizando

lu(S,thresh)

donde hay un umbral de pivote en [0,1].thresh La pivotante se produce cuando la entrada diagonal de una columna tiene una magnitud inferior a la de la magnitud de cualquier entrada de la subdiagonal en esa columna. fuerza la pivotante diagonal. es el valor predeterminado.threshthresh = 0thresh = 1 (El valor predeterminado es para la sintaxis de cuatro resultados).thresh0.1

Cuando se llama con tres o menos salidas, asigna automáticamente la memoria necesaria para contener la dispersa y los factores durante la factorización.luMATLABLU A excepción de la sintaxis de cuatro resultados, no utiliza ninguna prefactorización de LU simbólica para determinar los requisitos de memoria y configurar las estructuras de datos con antelación.MATLAB

Reordenación y factorización. Este ejemplo muestra los efectos de reordenación y factorización en matrices dispersas.

Si obtiene una buena permutación de columna que reduce el llenado, quizás de o, entonces la computación toma menos tiempo y almacenamiento que la computación.psymrcmcolamdlu(S(:,p))lu(S)

Crea una matriz dispersa usando el ejemplo de bola Bucky.

B = bucky;

tiene exactamente tres elementos distintos de cero en cada fila y columna.B

Cree dos permutaciones y use y, respectivamente.rmsymrcmsymamd

r = symrcm(B); m = symamd(B);

Las dos permutaciones son la orden simétrica inversa Cuthill-McKee y la ordenación simétrica de grado mínimo aproximado.

Cree tramas de espionaje para mostrar las tres matrices de adyacencia del gráfico Bucky Ball con estos tres numeros diferentes. La estructura local, basada en el Pentágono, de la numeración original no es evidente en los demás.

figure subplot(1,3,1) spy(B) title('Original')  subplot(1,3,2) spy(B(r,r)) title('Reverse Cuthill-McKee')  subplot(1,3,3) spy(B(m,m)) title('Min Degree')

El orden inverso Cuthill-McKee, reduce el ancho de banda y concentra todos los elementos distintos de cero cerca de la diagonal.r El orden de grado mínimo aproximado,, produce una estructura como fractal con grandes bloques de ceros.m

Para ver el relleno generado en la factorización LU de la bola Bucky, utilice, la matriz de identidad dispersa, para insertar-3S en la diagonal de.speyeB

B = B - 3*speye(size(B));

Puesto que cada suma de filas es ahora cero, este nuevo es realmente singular, pero sigue siendo instructivo para calcular su factorización LU.B Cuando se llama con un solo argumento de salida, devuelve los dos factores triangulares y, en una sola matriz dispersa.luLU El número de ceros en esa matriz es una medida del tiempo y el almacenamiento necesarios para resolver los sistemas lineales que implican.B

Estos son los recuentos distintos de cero para las tres permutaciones que se están considerando.

(Original):lu(B) 1022
(Reverso Cuthill-McKee):lu(B(r,r)) 968
(Grado mínimo aproximado):lu(B(m,m)) 636

Aunque este es un pequeño ejemplo, los resultados son típicos. El esquema de numeración original lleva a la mayoría del llenado. El llenado de la orden inversa Cuthill-McKee se concentra dentro de la banda, pero es casi tan extenso como las dos primeras órdenes. Para el orden de grado mínimo aproximado, los bloques relativamente grandes de ceros se conservan durante la eliminación y la cantidad de llenado es significativamente menor que la generada por los otros ordenamientos.

Las parcelas siguientes reflejan las características de cada reordenación.spy

figure subplot(1,3,1) spy(lu(B)) title('Original')  subplot(1,3,2) spy(lu(B(r,r))) title('Reverse Cuthill-McKee')  subplot(1,3,3) spy(lu(B(m,m))) title('Min Degree')

Factorización Cholesky

Si es una matriz simétrica (o Hermitiana), positiva, definida y dispersa, la siguiente instrucción devuelve una matriz triangular superior dispersa para que.SRR'*R = S

R = chol(S)

no pivota automáticamente para la dispersión, pero se puede calcular el grado mínimo aproximado y permutaciones de límite de perfil para su uso con.cholchol(S(p,p))

Dado que el algoritmo de Cholesky no utiliza pivotar para la dispersión y no requiere pivotar para la estabilidad numérica, hace un cálculo rápido de la cantidad de memoria necesaria y asigna toda la memoria al principio de la factorización.chol Puede utilizar, que utiliza el mismo algoritmo que, para calcular cuánta memoria se asigna.symbfactchol

La factorización de QR

calcula la factorización QR completa de una matriz dispersa con oMATLABS

 [Q,R] = qr(S)

[Q,R,E] = qr(S)

pero esto es a menudo poco práctico. La matriz unitaria a menudo no tiene una alta proporción de cero elementos.Q Una alternativa más práctica, a veces conocida como "la factorización QR Q-Less," está disponible.

Con un argumento de entrada disperso y un argumento de salida

R = qr(S)

Devuelve solo la porción triangular superior de la factorización de QR. La matriz proporciona una factorización de Cholesky para la matriz asociada con las ecuaciones normales:R

R'*R = S'*S

Sin embargo, se evita la pérdida de información numérica inherente al cómputo.S'*S

Con dos argumentos de entrada que tienen el mismo número de filas y dos argumentos de salida, la instrucción

[C,R] = qr(S,B)

aplica las transformaciones ortogonales a, produciendo sin computación.BC = Q'*BQ

La factorización QR sin Q permite la solución de problemas de mínimos cuadrados dispersos

$minimize {‖ A x - b ‖}_{2}$

con dos pasos:

[c,R] = qr(A,b); x = R\c

Si es disperso, pero no cuadrado, utiliza estos pasos para la ecuación lineal que resuelve el operador de barra diagonal inversa:AMATLAB

x = A\b

O, usted puede hacer la factorización usted mismo y examinar paraR deficiencia de rango.

También es posible resolver una secuencia de sistemas lineales de mínimos cuadrados con diferentes lados de la derecha, que no son necesariamente conocidos cuando se calcula.bR = qr(A) El enfoque resuelve las "ecuaciones semi-normales conR'*R*x = A'*b

x = R\(R'\(A'*b))

y luego emplea un paso de refinamiento iterativo para reducir el error de redondeo:

r = b - A*x; e = R\(R'\(A'*r)); x = x + e

Factorizaciones incompletas

Las funciones y proporcionan las factorizaciones aproximadas, que son útiles como preacondicionadores para los métodos iterativos dispersos.iluichol incomplete

La función produce tres factorizaciones (ILU): la (), una versión de Crout de ILU () e ILU con umbral de caída y pivotante ().iluparte inferior incompletaILU de relleno ceroILU(0)ILUC(tau)ILUTP(tau) Los pivotes nunca y los factores resultantes sólo tienen ceros en las posiciones donde la matriz de entrada tenía ceros.ILU(0) Ambos y, sin embargo, la caída basada en umbrales con la tolerancia de gota definida por el usuario.ILUC(tau)ILUTP(tau)tau

Por ejemplo:

A = gallery('neumann', 1600) + speye(1600);

ans =          7840

nnz(lu(A))

ans =        126478

muestra que tiene 7840 nonceros, y su factorización completa LU tiene 126478 nonceros.A Por otro lado, el siguiente código muestra las diferentes salidas ILU:

[L,U] = ilu(A); nnz(L)+nnz(U)-size(A,1)

ans =          7840

norm(A-(L*U).*spones(A),'fro')./norm(A,'fro')

ans =     4.8874e-17

opts.type = 'ilutp'; opts.droptol = 1e-4; [L,U,P] = ilu(A, opts); nnz(L)+nnz(U)-size(A,1)

ans =         31147

norm(P*A - L*U,'fro')./norm(A,'fro')

ans =     9.9224e-05

opts.type = 'crout'; [L,U,P] = ilu(A, opts); nnz(L)+nnz(U)-size(A,1)

ans =         31083

norm(P*A-L*U,'fro')./norm(A,'fro')

ans =     9.7344e-05

Estos cálculos muestran que los factores de cero-relleno tienen 7840 nonceros, los factores tienen 31147 nonceros, y los factores tienen 31083 nonceros.ILUTP(1e-4)ILUC(1e-4) Además, el error relativo del producto de los factores de relleno cero es esencialmente cero en el patrón de.A Por último, el error relativo en las factorizaciones producidas con umbral de caída está en el mismo orden de la tolerancia a caídas, aunque esto no se garantiza que se produzca. Consulte la página de referencia para obtener más opciones y detalles.ilu

La función proporciona () así como el umbral basado en la caída de factorizaciones incompletas de Cholesky () de matrices dispersas, positivas y definidas.icholfactorizaciones de Cholesky incompletas de relleno ceroIC(0)ICT(tau) Estas factorizaciones son los análogos de las factorizaciones de LU incompletas arriba y tienen muchas de las mismas características. Por ejemplo: muestra que tiene 195228 nonceros, y su factorización completa de Cholesky sin reordenar tiene 7762589 nonceros.

A = delsq(numgrid('S',200)); nnz(A)

ans =        195228

nnz(chol(A,'lower'))

ans =       7762589

A Por el contrario:

L = ichol(A); nnz(L)

ans =        117216

norm(A-(L*L').*spones(A),'fro')./norm(A,'fro')

ans =     3.5805e-17

opts.type = 'ict'; opts.droptol = 1e-4; L = ichol(A,opts); nnz(L)

ans =       1166754

norm(A-L*L','fro')./norm(A,'fro')

ans =     2.3997e-04

tiene no ceros sólo en el patrón del triángulo inferior de, y en el patrón de, el producto de los factores coincide.IC(0)AA Además, los factores son considerablemente más más disperso que el factor Cholesky completo, y el error relativo entre y está en el mismo orden de la tolerancia a caídas.ICT(1e-4)A L*L' Es importante tener en cuenta que a diferencia de los factores proporcionados por, los factores predeterminados proporcionados por son más bajos triangulares.cholichol Consulte la página de referencia para obtener más información.ichol

Sistemas de ecuaciones lineales

Existen dos clases diferentes de métodos para resolver sistemas de ecuaciones lineales simultáneas:

suelen ser variantes de la eliminación Gaussiana.Direct methods Estos métodos implican los elementos individuales de la matriz directamente, a través de operaciones matriciales como LU o la factorización de Cholesky. Implementa métodos directos a través de los operadores de división Matrix/y \, que puede utilizar para resolver sistemas lineales.MATLAB
producir sólo una solución aproximada después de un número finito de pasos.Los métodos iterativos Estos métodos implican la matriz de coeficiente sólo indirectamente, a través de un producto vector matriz o un operador lineal abstracto. Los métodos iterativos se suelen aplicar solo a matrices dispersas.

Métodos directos

Los métodos directos suelen ser más rápidos y generalmente aplicables que los métodos indirectos, si hay suficiente espacio de almacenamiento disponible para llevarlos a cabo. Los métodos iterativos suelen ser aplicables a los casos restringidos de ecuaciones y dependen de propiedades como el dominio diagonal o la existencia de un operador diferencial subyacente. Los métodos directos se implementan en el núcleo del software y se hacen lo más eficientes posible para las clases generales de matrices.MATLAB Los métodos iterativos generalmente se implementan en los archivos en el idioma y pueden utilizar la solución directa de subproblemas o preacondicionadores.MATLAB

Utilizando una orden de preordenación diferente. Si no es diagonal, con bandas, triangular o una permutación de una matriz triangular, la barra diagonal inversa (\) reordena los índices para reducir la cantidad de llenado, es decir, el número de entradas que no son de cero que se agregan a las matrices de factorización dispersas.AA El nuevo orden, llamado a, se realiza antes de la factorización de.preorderingA En algunos casos, es posible que pueda proporcionar un mejor preordenamiento que el utilizado por el algoritmo de barra diagonal inversa.

Para utilizar un orden previo diferente, primero desactive las dos preórdenes automáticas que la barra diagonal inversa puede realizar de forma predeterminada, utilizando la función de la siguiente manera:spparms

defaultParms = spparms; spparms('autoamd',0); spparms('autommd',0);

Ahora, suponiendo que ha creado un vector de permutación que especifica un preordenamiento de los índices de, aplique la barra diagonal inversa a la matriz, cuyas columnas son las columnas de, permute según el vector.pAA(:,p)Ap

x = A(:,p) \ b; x(p) = x; spparms(currentParms);

El comando restaura los controles a su estado anterior, en caso de que lo use más adelante sin especificar un orden previo adecuado.spparms(defaultParms)A\b

Métodos iterativos

Hay once funciones disponibles que implementan métodos iterativos para sistemas dispersos de sistemas lineales simultáneos.

Funciones para métodos iterativos para sistemas dispersos

Función	Método
`bicg`	Gradiente biconjugado
`bicgstab`	Gradiente biconado estabilizado
`bicgstabl`	Gradiente biconado estabilizado (l)
`cgs`	Conjugada gradiente cuadrado
`gmres`	Residuo mínimo generalizado
`lsqr`	Los cuadrados mínimos
`minres`	Residuo mínimo
`pcg`	Gradiente conjugada preacondicionados
`qmr`	Quasiminimal residual
`symmlq`	LQ simétrica
`tfqmr`	Sin transposición quasiminimal residual

Estos métodos están diseñados para resolver = o minimizar la norma de –.AxbbAx Para el método de degradado conjugada precondicionada, debe ser una matriz definida simétrica y positiva. y se puede utilizar en matrices indefinidas simétricas.pcgAminressymmlq Para, la matriz no tiene por qué ser cuadrada.lsqr Los otros siete pueden manejar matrices cuadradas no simétricas y cada método tiene un beneficio distintivo.

Todos los once métodos pueden hacer uso de preacondicionadores. El sistema lineal

$A x = b$

se sustituye por el sistema equivalente

$M^{- 1} A x = M^{- 1} b$

El preacondicionador se elige para acelerar la convergencia del método iterativo.M En muchos casos, los preacondicionadores se producen naturalmente en el modelo matemático. Una ecuación diferencial parcial con coeficientes variables se puede aproximar por uno con coeficientes constantes, por ejemplo. Las factorizaciones de matrices incompletas se pueden utilizar en ausencia de preacondicionadores naturales.

La aproximación de la diferencia finita de cinco puntos a la ecuación de Laplace en un cuadrado, dominio bidimensional proporciona un ejemplo. Las siguientes instrucciones utilizan el método de degradado conjugada precondicionada = * ', donde es el factor de Colesky incompleto de relleno cero de.MLLLA

A = delsq(numgrid('S',50)); b = ones(size(A,1),1); tol = 1e-3; maxit = 100; L = ichol(A); [x,flag,err,iter,res] = pcg(A,b,tol,maxit,L,L');

Se requieren veintiún iteraciones para lograr la precisión prescrita. Por otro lado, el uso de un preacondicionador diferente puede producir mejores resultados. Por ejemplo, utilizando para construir un Cholesky incompleto modificado, la precisión prescrita se cumple después de sólo 15 iteraciones:ichol

L = ichol(A,struct('type','nofill','michol','on')); [x,flag,err,iter,res] = pcg(A,b,tol,maxit,L,L');

La información de fondo sobre estos métodos iterativos y las factorizaciones incompletas está disponible en y.[2][6]

Eigenvalues y valores singulares

Hay dos funciones disponibles que calculan algunos valores autovalores o singulares. se basa en.svdseigs

Funciones para calcular algunos eigenvalues o valores singulares

Función	Descripción
`eigs`	Pocos valores autovalores
`svds`	Pocos valores singulares

Estas funciones se utilizan con más frecuencia con matrices dispersas, pero se pueden utilizar con matrices completas o incluso con operadores lineales definidos en el código.MATLAB

La declaración

[V,lambda] = eigs(A,k,sigma)

encuentra los valores propios y los autovectores correspondientes de la matriz que están más cerca del "turno".kAsigma Si se omite, se encuentran los valores autovalores más grandes en magnitud.sigma Si es cero, se encuentran los valores autovalores más pequeños en magnitud.sigma Una segunda matriz,,, se puede incluir para el problema generalizado del valor propio:B Aυ = λBυ.

La declaración

[U,S,V] = svds(A,k)

encuentra los valores singulares más grandes de ykA

[U,S,V] = svds(A,k,'smallest')

encuentra los valores singulares más pequeños.k

Este ejemplo muestra cómo encontrar el valor propio más pequeño y el autovector de una matriz dispersa.

Configure el operador de diferencia Laplaciana de cinco puntos en una cuadrícula de 65-por-65 en un dominio bidimensional en forma de un.L

L = numgrid('L',65); A = delsq(L);

Determine el orden y el número de elementos distintos de cero.

size(A)

ans = 1×2

        2945        2945

nnz(A)

ans = 14473

es una matriz de orden 2945 con 14.473 elementos distintos de cero.A

Calcule el valor propio más pequeño y el autovector.

[v,d] = eigs(A,1,0);

Distribuya los componentes del autovector sobre los puntos de rejilla apropiados y produzca una gráfica de contorno del resultado.

L(L>0) = full(v(L(L>0))); x = -1:1/32:1; contour(x,x,L,15) axis square

Las técnicas numéricas utilizadas en y se describen en.eigssvds[6]

Referencias

[1] Amestoy, P. R., T. A. Davis, and I. S. Duff, “An Approximate Minimum Degree Ordering Algorithm,” SIAM Journal on Matrix Analysis and Applications, Vol. 17, No. 4, Oct. 1996, pp. 886-905.

[2] Barrett, R., M. Berry, T. F. Chan, et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, 1994.

[3] Davis, T.A., Gilbert, J. R., Larimore, S.I., Ng, E., Peyton, B., “A Column Approximate Minimum Degree Ordering Algorithm,” Proc. SIAM Conference on Applied Linear Algebra, Oct. 1997, p. 29.

[4] Gilbert, John R., Cleve Moler, and Robert Schreiber, “Sparse Matrices in MATLAB: Design and Implementation,” SIAM J. Matrix Anal. Appl., Vol. 13, No. 1, January 1992, pp. 333-356.

[5] Larimore, S. I., An Approximate Minimum Degree Column Ordering Algorithm, MS Thesis, Dept. of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, 1998.

[6] Saad, Yousef, Iterative Methods for Sparse Linear Equations. PWS Publishing Company, 1996.

[7] Karypis, George and Vipin Kumar. "A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs." SIAM Journal on Scientific Computing. Vol. 20, Number 1, 1999, pp. 359–392.