Calcolare il numero di sopradiagonali di una sottomatrice

[Lory314]

Ciao a tutti. Ho il seguente problema: data una matrice a banda $A \in \mathbb{R}^{N\times N}$ con $KD$ sopradiagonalI (esclusa quindi quella principale) e un vettore $v$, considerare la sottomatrice $R$ di $A$ che si ottiene estraendo gli elementi in posizione $v_i,v_j$ con $i,j=1,\ldots,N$. Vorrei costruire un algoritmo per determinare A PRIORI il numero di sopradiagonali non nulle di $R$, ossia vorrei conoscere il numero di sopradiagonali di $R$ senza conoscere $R$.
Esempio:

$N=6, KD=2$

$ A=( ( 1 , 2 , 3 , 0 , 0 , 0 ),( 2 , 3 , 4 , 5 , 0 , 0 ),( 3 , 4 , 5 , 6 , 7 , 0 ),( 0 , 5 , 6 , 7 , 8 , 9 ),( 0 , 0 , 7 , 8 , 9 , 10 ),( 0 , 0 , 0 , 9 , 10 , 11 ) ) $

$v=(1,3,4)$

$R = ((1,3,0),(3,5,6),(0,6,7))$

Il questo esempio il numero di sopradiagonali di $R$ è $1$.

La mia idea è stata la seguente: il numero di sopradiagonali, esclusa la principale, è dato dal numero di elementi di $v$ che sono minori di $KD+1$ meno $1$.
In matlab questo si ottiene facilmente con

sum(v < KD+1)-1

Purtroppo però questo ragionamento non funziona sempre (ho trovato un controesempio a mano e testato con il codice), ma su molti esempi sì. Questo mi fa pensare di essere sulla strada giusta.

Qualcuno ha suggerimenti, consigli, idee, anche completamente diverse dalla mia?

Grazie




P.S.: chiedo scusa se la sezione è sbagliata

[Lory314]

Forse sono riuscito a risolvere il problema.
L'idea è la seguente: per ogni elemento del vettore $v(i)$ scorro tutti gli elementi $v(j)$ successivi all'elemento $v(i)$ (compreso $v(i)$), verifico se l'indice $v(j)$ sta nella banda di $A$, conto quanti sono gli elementi della riga $v(i)$ che soddisfano questa proprietà e salvo i valori così ottenuti in un vettore $d$. Questo vettore contiene nella posizione $i$ la distanza massima di un elemento sulla riga $v(i)$ dalla diagonale. Il massimo di questo vettore quindi restiutisce l'indice della colonna contenente l'elemento più distante dalla diagonale. Poiché per convenzione la posizione della diagonale principale è $0$, sottraggo $1$.
Ho espresso questo procedimento nella seguente function matlab/octave:

function KKD=numdiag(A,KD,v,N)
	d=zeros(1,length(v));
	for i=1:length(v)
		for j=i:length(v)
			if(and( v(i)<=v(j), v(j)<=min(N,KD+v(i)))) % qui devo verificare se l'elemento stà nella banda
				d(i)=d(i)+1;
			end
		end
	end
	KKD=max(d)-1;
	
end

Questo codice sembra funzionare sugli tutti gli esempi che ho provato, anche quelli in cui il codice precedente falliva. La mia paura è che dovendo fare due cicli innestati possa essere poco efficiente quando il vettore $v$ è grande. Ora provo a fare qualche test, ma se qualcuno avesse consigli o notasse qualche errore, non esiti a rispondere.